1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/docs/wiki/Directories Sun Jun 12 00:00:12 2022 +0200
1.3 @@ -0,0 +1,273 @@
1.4 += Directories =
1.5 +
1.6 +Filesystem directories contain collections of files, other directories, along
1.7 +with other filesystem objects. Directories can be listed, permitting
1.8 +filesystem clients to peruse the contents of each directory. However, the act
1.9 +of listing a directory may impose certain constraints on the operations being
1.10 +conducted on the directory during the listing process.
1.11 +
1.12 +Operations that affect directory contents include the following:
1.13 +
1.14 + * Creating a new object
1.15 + * Removing an object
1.16 + * Moving an object out of the directory
1.17 + * Moving an object into the directory
1.18 +
1.19 +It is conceivable that for some filesystems, these operations will not be able
1.20 +to rely on directly modifying the directory since a listing operation may be
1.21 +in progress. Consequently, a number of rules would be imposed for such
1.22 +filesystems. It appears that Ext2-based filesystems accessed via libext2fs do
1.23 +not require such rules to be applied outside the library due to the design of
1.24 +the filesystem structures and the behaviour of the library itself.
1.25 +
1.26 +== Providers ==
1.27 +
1.28 +Providers of filesystem objects are created when at least one filesystem
1.29 +client is accessing such an object, with the object regarded as being
1.30 +'''open'''. By definition, a provider will exist until all clients have closed
1.31 +or discarded their means of accessing the object.
1.32 +
1.33 +An object is regarded as '''accessible''' if it can still be opened by
1.34 +filesystem clients. Where an object has been removed, it will no longer be
1.35 +accessible since clients should not be able to see the object in the
1.36 +filesystem any more. (The actual filesystem residing in storage may not have
1.37 +been updated for such a removal, this being the eventual outcome of a removal
1.38 +operation.)
1.39 +
1.40 +Providers can be regarded as '''accessible''' if they maintain access to
1.41 +objects that are open and accessible. Clients opening objects will only gain
1.42 +access to accessible providers. Providers can become inaccessible if an object
1.43 +is removed even if the object (and its provider) is still open.
1.44 +
1.45 +Initially, providers will correspond to objects resident in the stored
1.46 +filesystem. Thus, looking up an object using its path will involve the
1.47 +filesystem, yielding a file identifier that can be used to map to a provider.
1.48 +
1.49 +{{{
1.50 +def get_provider_from_filesystem(path):
1.51 + fileid = opening.get_fileid(path)
1.52 +
1.53 + if not fileid:
1.54 + return error
1.55 +
1.56 + return find_provider(fileid)
1.57 +}}}
1.58 +
1.59 +However, providers may not always immediately correspond to objects resident
1.60 +in the stored filesystem. Where an object is created but cannot be immediately
1.61 +registered in the contents of a directory, it must be registered separately
1.62 +and attempts to open this object must consult this separate mapping of
1.63 +filenames to providers.
1.64 +
1.65 +{{{
1.66 +def get_provider(path):
1.67 + provider = find_created_provider(path)
1.68 +
1.69 + if provider:
1.70 + return provider
1.71 +
1.72 + return get_provider_from_filesystem(path)
1.73 +}}}
1.74 +
1.75 +Providers that are inaccessible need to be retained until they are closed.
1.76 +However, since they are no longer accessible, they should not be available to
1.77 +the provider lookup operations.
1.78 +
1.79 +When providers are closed, they are removed from any mapping in which they
1.80 +could be found. Inaccessible providers that have been retained outside the
1.81 +identifier or filename mappings will represent objects that should be removed
1.82 +from their parent directory. Accessible providers retained by the mappings
1.83 +will represent objects that should be created in their parent directory.
1.84 +
1.85 +Whether object removal or creation will occur depends on whether the parent
1.86 +directory is able to safely perform these operations concurrently with other
1.87 +operations (such as servicing a listing operation) or whether such operations
1.88 +will need to be deferred until they can be safely performed.
1.89 +
1.90 +== Object Removal ==
1.91 +
1.92 +Filesystem object removal involves obtaining any provider of the object. Where
1.93 +a provider can be obtained, it will be made inaccessible and removal will be
1.94 +requested. The actual object will not be removed at least until it is closed
1.95 +because it may still receive and provide data. (Unlinking open files is a
1.96 +feature of Unix systems.)
1.97 +
1.98 +Where a provider cannot be obtained, an attempt will be made to obtain the
1.99 +parent directory provider, and if this succeeds, it indicates that the
1.100 +directory is being accessed and must therefore be notified of the intention to
1.101 +eventually remove the object concerned.
1.102 +
1.103 +Without any provider of the object, and where no directory provider can be
1.104 +obtained, the object can be immediately removed from the filesystem.
1.105 +
1.106 +{{{
1.107 +def remove_object(path):
1.108 + provider = get_provider(path)
1.109 +
1.110 + if provider:
1.111 + return make_provider_inaccessible(provider)
1.112 +
1.113 + dirname, basename = split(path)
1.114 + directory_provider = get_provider(dirname)
1.115 +
1.116 + if directory_provider:
1.117 + return directory_provider.remove_pending(basename)
1.118 +
1.119 + return filesystem.remove_object(path)
1.120 +}}}
1.121 +
1.122 +It should be noted that with no accessible provider, any attempt to create a
1.123 +file with the same name as a removed file should cause a new "version" of the
1.124 +file to be created.
1.125 +
1.126 +== Object Creation ==
1.127 +
1.128 +Filesystem object creation occurs when no existing provider can be found for a
1.129 +named object and where creation is requested. Any new object will be
1.130 +accessible and remain so until or unless it is removed.
1.131 +
1.132 +Whether an object is created in the filesystem storage depends on whether the
1.133 +parent directory is being used.
1.134 +
1.135 +If a parent directory is not being used, the object can be registered in its
1.136 +proper location in the filesystem itself, yielding a file identifier.
1.137 +
1.138 +If a parent directory is being used, the object cannot be immediately
1.139 +registered in its proper location, but since data may still need to be written
1.140 +to storage, a temporary location is employed, yielding a file identifier.
1.141 +
1.142 +For an object created in a temporary location, a temporary mapping from the
1.143 +path of the object to the provider is established, with the parent directory
1.144 +being notified of the pending object creation.
1.145 +
1.146 +{{{
1.147 +def create_object(path):
1.148 + provider = get_provider(path)
1.149 +
1.150 + if provider:
1.151 + return error
1.152 +
1.153 + dirname, basename = split(path)
1.154 + directory_provider = get_provider(dirname)
1.155 +
1.156 + if directory_provider:
1.157 + provider = make_provider(get_temporary_location(path))
1.158 + directory_provider.create_pending(provider)
1.159 + return register_created_provider(path, provider)
1.160 +
1.161 + provider = make_provider(path)
1.162 + return register_provider(provider)
1.163 +}}}
1.164 +
1.165 +== Created Providers ==
1.166 +
1.167 +Created providers are retained by the registry until their files can be
1.168 +committed to the filesystem in the desired location.
1.169 +
1.170 +The `register_created_provider` operation establishes a mapping from a path to
1.171 +a provider that can be queried using the `find_created_provider` operation.
1.172 +
1.173 +Created providers are deregistered when they are closed. This will occur when
1.174 +the parent directory of the file to be committed is closed. At that time, the
1.175 +created file will be moved from its temporary location to the desired
1.176 +location.
1.177 +
1.178 +== Inaccessible Providers ==
1.179 +
1.180 +Inaccessible providers are retained by the registry until they are closed.
1.181 +
1.182 +Where the provided file resides in a non-temporary location, closure will
1.183 +occur when the parent directory of the provided file is closed, this having
1.184 +obstructed the removal of the file. At that time, the provided file will be
1.185 +removed.
1.186 +
1.187 +Where the provided file resides in a temporary location, closure will not be
1.188 +obstructed by any directory and will cause the file to be removed immediately.
1.189 +
1.190 +== Directory Provider Closure ==
1.191 +
1.192 +A critical event that typically initiates housekeeping work for created and
1.193 +removed files is the closure of the parent directory of those files.
1.194 +
1.195 +Directory providers support the `create_pending` and `remove_pending`
1.196 +operations that register the details of affected files. When closure occurs,
1.197 +the provider will contact the registry to initiate the necessary work to
1.198 +relocate created files and to remove files.
1.199 +
1.200 +
1.201 +
1.202 +
1.203 + Where an object provider is notified of pending removal, it will initiate
1.204 + removal of the actual object upon closure, checking for an active parent
1.205 + provider.
1.206 +
1.207 + Where a parent provider is notified of pending removal, it will initiate
1.208 + removal of the actual object upon closure, checking for an active object
1.209 + provider.
1.210 +
1.211 + Object opening logic would need to be adjusted. Consider the case where a
1.212 + file is removed but still open.
1.213 +
1.214 + Any attempt to open a file with the same name must ignore the original and
1.215 + open a new file of that name which would be stored elsewhere until such
1.216 + time as the original is actually removed from its location.
1.217 +
1.218 + This new file might have a different identifier since the original file
1.219 + would still exist and retain the identifier.
1.220 +
1.221 + Any such new, but uncommitted, file must be accessible by other clients
1.222 + attempting to open a file of that name. However, removal operations must
1.223 + also be possible, making this version of the open file also unaccessible
1.224 + to new opening clients.
1.225 +
1.226 + Therefore, any providers used by opening clients must only refer to a
1.227 + version of a file that is pending removal if no other version has been
1.228 + created. Once a new version has been created, any provider pending removal
1.229 + must be relegated to a separate collection.
1.230 +
1.231 + Storage of new versions of files could be confined to special directories
1.232 + that are hidden from clients.
1.233 +
1.234 + The opening logic would be as follows:
1.235 +
1.236 + provider = find_provider(path)
1.237 +
1.238 + if provider:
1.239 + if provider.pending_removal():
1.240 + relegate(provider)
1.241 + provider = create_provider(path, hidden=True)
1.242 + else:
1.243 + provider = create_provider(path, hidden=False)
1.244 +
1.245 + # Have provider.
1.246 +
1.247 + return provider.make_resource()
1.248 +
1.249 + A provider would normally be obtained by consulting the filesystem
1.250 + implementation. However, new versions of files replacing ones pending
1.251 + removal will reside in locations that are different to the intended
1.252 + location of the file. Consequently, the registry needs to maintain its own
1.253 + mapping of paths to providers for such file versions.
1.254 +
1.255 + The opportunity to remove a file definitively arises when the following
1.256 + conditions are satisfied:
1.257 +
1.258 + * The parent directory is not open in some way
1.259 + * The original provider for the file is no longer open
1.260 +
1.261 + For new versions of a removed file that have themselves been marked as
1.262 + pending removal, their closure is sufficient to remove their filesystem
1.263 + resources.
1.264 +
1.265 + However, the registry must maintain a path entry for any active version
1.266 + of a removed file until that version is closed. Thus, the following
1.267 + conditions apply:
1.268 +
1.269 + * The parent directory (of the original file) is not open in some way
1.270 + * The provider of the new version is no longer open
1.271 +
1.272 + It will not be generally possible to open the hidden directory containing
1.273 + new file versions. Therefore, the transfer of the file to its intended
1.274 + location will not risk interfering with any operations on the hidden
1.275 + directory.
1.276 +