diff options
Diffstat (limited to 'doc/html/TechNotes/SymbolTables.html')
| -rw-r--r-- | doc/html/TechNotes/SymbolTables.html | 329 |
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> |