summaryrefslogtreecommitdiffstats
path: root/doc/html/TechNotes/SymbolTables.html
diff options
context:
space:
mode:
Diffstat (limited to 'doc/html/TechNotes/SymbolTables.html')
-rw-r--r--doc/html/TechNotes/SymbolTables.html329
1 files changed, 329 insertions, 0 deletions
diff --git a/doc/html/TechNotes/SymbolTables.html b/doc/html/TechNotes/SymbolTables.html
new file mode 100644
index 0000000..05ee538
--- /dev/null
+++ b/doc/html/TechNotes/SymbolTables.html
@@ -0,0 +1,329 @@
+<html>
+<body>
+
+<h1>Symbol Table Caching Issues</h1>
+
+<pre>
+
+A number of issues involving caching of object header messages in
+symbol table entries must be resolved.
+
+What is the motivation for these changes?
+
+ If we make objects completely independent of object name it allows
+ us to refer to one object by multiple names (a concept called hard
+ links in Unix file systems), which in turn provides an easy way to
+ share data between datasets.
+
+ Every object in an HDF5 file has a unique, constant object header
+ address which serves as a handle (or OID) for the object. The
+ object header contains messages which describe the object.
+
+ HDF5 allows some of the object header messages to be cached in
+ symbol table entries so that the object header doesn't have to be
+ read from disk. For instance, an entry for a directory caches the
+ directory disk addresses required to access that directory, so the
+ object header for that directory is seldom read.
+
+ If an object has multiple names (that is, a link count greater than
+ one), then it has multiple symbol table entries which point to it.
+ All symbol table entries must agree on header messages. The
+ current mechanism is to turn off the caching of header messages in
+ symbol table entries when the header link count is more than one,
+ and to allow caching once the link count returns to one.
+
+ However, in the current implementation, a package is allowed to
+ copy a symbol table entry and use it as a private cache for the
+ object header. This doesn't work for a number of reasons (all but
+ one require a `delete symbol entry' operation).
+
+ 1. If two packages hold copies of the same symbol table entry,
+ they don't notify each other of changes to the symbol table
+ entry. Eventually, one package reads a cached message and
+ gets the wrong value because the other package changed the
+ message in the object header.
+
+ 2. If one package holds a copy of the symbol table entry and
+ some other part of HDF5 removes the object and replaces it
+ with some other object, then the original package will
+ continue to access the non-existent object using the new
+ object header.
+
+ 3. If one package holds a copy of the symbol table entry and
+ some other part of HDF5 (re)moves the directory which
+ contains the object, then the package will be unable to
+ update the symbol table entry with the new cached
+ data. Packages that refer to the object by the new name will
+ use old cached data.
+
+
+The basic problem is that there may be multiple copies of the object
+symbol table entry floating around in the code when there should
+really be at most one per hard link.
+
+ Level 0: A copy may exist on disk as part of a symbol table node, which
+ is a small 1d array of symbol table entries.
+
+ Level 1: A copy may be cached in memory as part of a symbol table node
+ in the H5Gnode.c file by the H5AC layer.
+
+ Level 2a: Another package may be holding a copy so it can perform
+ fast lookup of any header messages that might be cached in
+ the symbol table entry. It can't point directly to the
+ cached symbol table node because that node can dissappear
+ at any time.
+
+ Level 2b: Packages may hold more than one copy of a symbol table
+ entry. For instance, if H5D_open() is called twice for
+ the same name, then two copies of the symbol table entry
+ for the dataset exist in the H5D package.
+
+How can level 2a and 2b be combined?
+
+ If package data structures contained pointers to symbol table
+ entries instead of copies of symbol table entries and if H5G
+ allocated one symbol table entry per hard link, then it's trivial
+ for Level 2a and 2b to benefit from one another's actions since
+ they share the same cache.
+
+How does this work conceptually?
+
+ Level 2a and 2b must notify Level 1 of their intent to use (or stop
+ using) a symbol table entry to access an object header. The
+ notification of the intent to access an object header is called
+ `opening' the object and releasing the access is `closing' the
+ object.
+
+ Opening an object requires an object name which is used to locate
+ the symbol table entry to use for caching of object header
+ messages. The return value is a handle for the object. Figure 1
+ shows the state after Dataset1 opens Object with a name that maps
+ through Entry1. The open request created a copy of Entry1 called
+ Shadow1 which exists even if SymNode1 is preempted from the H5AC
+ layer.
+
+ ______
+ Object / \
+ SymNode1 +--------+ |
+ +--------+ _____\ | Header | |
+ | | / / +--------+ |
+ +--------+ +---------+ \______/
+ | Entry1 | | Shadow1 | /____
+ +--------+ +---------+ \ \
+ : : \
+ +--------+ +----------+
+ | Dataset1 |
+ +----------+
+ FIGURE 1
+
+
+
+ The SymNode1 can appear and disappear from the H5AC layer at any
+ time without affecting the Object Header data cached in the Shadow.
+ The rules are:
+
+ * If the SymNode1 is present and is about to disappear and the
+ Shadow1 dirty bit is set, then Shadow1 is copied over Entry1, the
+ Entry1 dirty bit is set, and the Shadow1 dirty bit is cleared.
+
+ * If something requests a copy of Entry1 (for a read-only peek
+ request), and Shadow1 exists, then a copy (not pointer) of Shadow1
+ is returned instead.
+
+ * Entry1 cannot be deleted while Shadow1 exists.
+
+ * Entry1 cannot change directly if Shadow1 exists since this means
+ that some other package has opened the object and may be modifying
+ it. I haven't decided if it's useful to ever change Entry1
+ directly (except of course within the H5G layer itself).
+
+ * Shadow1 is created when Dataset1 `opens' the object through
+ Entry1. Dataset1 is given a pointer to Shadow1 and Shadow1's
+ reference count is incremented.
+
+ * When Dataset1 `closes' the Object the Shadow1 reference count is
+ decremented. When the reference count reaches zero, if the
+ Shadow1 dirty bit is set, then Shadow1's contents are copied to
+ Entry1, and the Entry1 dirty bit is set. Shadow1 is then deleted
+ if its reference count is zero. This may require reading SymNode1
+ back into the H5AC layer.
+
+What happens when another Dataset opens the Object through Entry1?
+
+ If the current state is represented by the top part of Figure 2,
+ then Dataset2 will be given a pointer to Shadow1 and the Shadow1
+ reference count will be incremented to two. The Object header link
+ count remains at one so Object Header messages continue to be cached
+ by Shadow1. Dataset1 and Dataset2 benefit from one another
+ actions. The resulting state is represented by Figure 2.
+
+ _____
+ SymNode1 Object / \
+ +--------+ _____\ +--------+ |
+ | | / / | Header | |
+ +--------+ +---------+ +--------+ |
+ | Entry1 | | Shadow1 | /____ \_____/
+ +--------+ +---------+ \ \
+ : : _ \
+ +--------+ |\ +----------+
+ \ | Dataset1 |
+ \________ +----------+
+ \ \
+ +----------+ |
+ | Dataset2 | |- New Dataset
+ +----------+ |
+ /
+ FIGURE 2
+
+
+What happens when the link count for Object increases while Dataset
+has the Object open?
+
+ SymNode2
+ +--------+
+ SymNode1 Object | |
+ +--------+ ____\ +--------+ /______ +--------+
+ | | / / | header | \ `| Entry2 |
+ +--------+ +---------+ +--------+ +--------+
+ | Entry1 | | Shadow1 | /____ : :
+ +--------+ +---------+ \ \ +--------+
+ : : \
+ +--------+ +----------+ \________________/
+ | Dataset1 | |
+ +----------+ New Link
+
+ FIGURE 3
+
+ The current state is represented by the left part of Figure 3. To
+ create a new link the Object Header had to be located by traversing
+ through Entry1/Shadow1. On the way through, the Entry1/Shadow1
+ cache is invalidated and the Object Header link count is
+ incremented. Entry2 is then added to SymNode2.
+
+ Since the Object Header link count is greater than one, Object
+ header data will not be cached in Entry1/Shadow1.
+
+ If the initial state had been all of Figure 3 and a third link is
+ being added and Object is open by Entry1 and Entry2, then creation
+ of the third link will invalidate the cache in Entry1 or Entry2. It
+ doesn't matter which since both caches are already invalidated
+ anyway.
+
+What happens if another Dataset opens the same object by another name?
+
+ If the current state is represented by Figure 3, then a Shadow2 is
+ created and associated with Entry2. However, since the Object
+ Header link count is more than one, nothing gets cached in Shadow2
+ (or Shadow1).
+
+What happens if the link count decreases?
+
+ If the current state is represented by all of Figure 3 then it isn't
+ possible to delete Entry1 because the object is currently open
+ through that entry. Therefore, the link count must have
+ decreased because Entry2 was removed.
+
+ As Dataset1 reads/writes messages in the Object header they will
+ begin to be cached in Shadow1 again because the Object header link
+ count is one.
+
+What happens if the object is removed while it's open?
+
+ That operation is not allowed.
+
+What happens if the directory containing the object is deleted?
+
+ That operation is not allowed since deleting the directory requires
+ that the directory be empty. The directory cannot be emptied
+ because the open object cannot be removed from the directory.
+
+What happens if the object is moved?
+
+ Moving an object is a process consisting of creating a new
+ hard-link with the new name and then deleting the old name.
+ This will fail if the object is open.
+
+What happens if the directory containing the entry is moved?
+
+ The entry and the shadow still exist and are associated with one
+ another.
+
+What if a file is flushed or closed when objects are open?
+
+ Flushing a symbol table with open objects writes correct information
+ to the file since Shadow is copied to Entry before the table is
+ flushed.
+
+ Closing a file with open objects will create a valid file but will
+ return failure.
+
+How is the Shadow associated with the Entry?
+
+ A symbol table is composed of one or more symbol nodes. A node is a
+ small 1-d array of symbol table entries. The entries can move
+ around within a node and from node-to-node as entries are added or
+ removed from the symbol table and nodes can move around within a
+ symbol table, being created and destroyed as necessary.
+
+ Since a symbol table has an object header with a unique and constant
+ file offset, and since H5G contains code to efficiently locate a
+ symbol table entry given it's name, we use these two values as a key
+ within a shadow to associate the shadow with the symbol table
+ entry.
+
+ struct H5G_shadow_t {
+ haddr_t stab_addr; /*symbol table header address*/
+ char *name; /*entry name wrt symbol table*/
+ hbool_t dirty; /*out-of-date wrt stab entry?*/
+ H5G_entry_t ent; /*my copy of stab entry */
+ H5G_entry_t *main; /*the level 1 entry or null */
+ H5G_shadow_t *next, *prev; /*other shadows for this stab*/
+ };
+
+ The set of shadows will be organized in a hash table of linked
+ lists. Each linked list will contain the shadows associated with a
+ particular symbol table header address and the list will be sorted
+ lexicographically.
+
+ Also, each Entry will have a pointer to the corresponding Shadow or
+ null if there is no shadow.
+
+ When a symbol table node is loaded into the main cache, we look up
+ the linked list of shadows in the shadow hash table based on the
+ address of the symbol table object header. We then traverse that
+ list matching shadows with symbol table entries.
+
+ We assume that opening/closing objects will be a relatively
+ infrequent event compared with loading/flushing symbol table
+ nodes. Therefore, if we keep the linked list of shadows sorted it
+ costs O(N) to open and close objects where N is the number of open
+ objects in that symbol table (instead of O(1)) but it costs only
+ O(N) to load a symbol table node (instead of O(N^2)).
+
+What about the root symbol entry?
+
+ Level 1 storage for the root symbol entry is always available since
+ it's stored in the hdf5_file_t struct instead of a symbol table
+ node. However, the contents of that entry can move from the file
+ handle to a symbol table node by H5G_mkroot(). Therefore, if the
+ root object is opened, we keep a shadow entry for it whose
+ `stab_addr' field is zero and whose `name' is null.
+
+ For this reason, the root object should always be read through the
+ H5G interface.
+
+One more key invariant: The H5O_STAB message in a symbol table header
+never changes. This allows symbol table entries to cache the H5O_STAB
+message for the symbol table to which it points without worrying about
+whether the cache will ever be invalidated.
+
+
+===========================================
+Last Modified: 8 July 1998 (technical content)
+Last Modified: 28 April 2000 (included in HDF5 Technical Notes)
+HDF Help Desk: hdfhelp@ncsa.uiuc.edu
+
+</pre>
+
+</body>
+</html>