diff options
Diffstat (limited to 'doc/html/TechNotes/SymbolTables.html')
| -rw-r--r-- | doc/html/TechNotes/SymbolTables.html | 329 |
1 files changed, 0 insertions, 329 deletions
diff --git a/doc/html/TechNotes/SymbolTables.html b/doc/html/TechNotes/SymbolTables.html deleted file mode 100644 index 05ee538..0000000 --- a/doc/html/TechNotes/SymbolTables.html +++ /dev/null @@ -1,329 +0,0 @@ -<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> |