--- /dev/null
+This file contains a threading analysis of Ubik prepared by
+Jeffrey Hutzelman and sent ot the openafs-devel@openafs.org
+mailing list in February 2011, archived at:
+https://lists.openafs.org/pipermail/openafs-devel/2011-February/018329.html
+
+INTRODUCTION
+
+ This document describes the structure of Ubik, with an eye toward
+ thread-safety and concurrency. It begins by discussing the elements,
+ usage, and locking considerations of major shared data structures. This
+ is followed by a discussion of each major subsystem. The emphasis is on
+ deficiencies in thread-safety and the changes needed to correct them.
+
+ Most of this document focuses on the user-mode Ubik server code, which
+ comprises the bulk of the Ubik library code and also of the complexity.
+ A separate section near the end is dedicated to Ubik client code, which
+ itself is intended primarily for use in user-mode applications. The
+ OpenAFS cache manager includes its own mechanisms for accessing
+ replicated services, including the Ubik-managed VLDB, and for tracking
+ the servers that provide them.
+
+ Occasionally, issues related to concurrency, performance, and modularity
+ (particularly as regards support for supporting multiple independent
+ databases in a single server process) are also discussed; however, these
+ discussions are peripheral and are included only to record data obtained
+ while examining the question of thread-safety and as a basis for future
+ work. Similarly, throughout this document are detailed discussions of
+ some parts of the code and certain data structures which, while not
+ always directly relevant to thread-safety, were produced in the course
+ of analyzing the Ubik library code. These are included to provide
+ additional background and as a basis for future work in documentation of
+ Ubik library internals and interfaces.
+
+
+MAJOR DATA STRUCTURES
+
+ This section calls out the major shared data structures used in the Ubik
+ server code and details what they are used for and how shared access to
+ them is protected. Much of this text is probably suitable as a starting
+ point for expanding on the documentation found in comments in ubik.p.h.
+
+ struct ubik_dbase - database
+
+ This structure contains nearly everything Ubik knows about an open
+ database (for an explanation of "nearly", see the section below on
+ globals), including database-wide parameters and state and a list of
+ active transactions.
+
+ The following structure elements are set only when the database
+ structure is being initialized, after which they are never modified:
+
+ + pathName - The base path used to construct database filenames
+ + physical later method pointers (read, write, truncate, sync,
+ stat, open, setlabel, getlabel, getnfiles), used to manipulate
+ the physical database files on disk. These currently always
+ point to the methods defined in phys.c, and in fact other
+ modules contain knowledge of the internal implementation of that
+ module.
+
+ The primary synchronization mechanism used to protect this structure
+ is the database lock (versionLock), which is manipulated via the
+ DBHOLD() and DBRELE() macros. This lock protects the following
+ structure elements, as well as a number of globals as described
+ elsewhere in this document:
+
+ + activeTrans - list of active transactions
+ + version - database version (*)
+ + tidCounter - transaction ID of latest transaction (*)
+ + writeTidCounter - transaction ID of latest write transaction (*)
+ + flags (*)
+ + readers
+
+ (*) These fields are currently protected by the database lock, except
+ that the beacon thread does not hold that lock when examining them,
+ or the global 'ubik_epochTime', which holds the corresponding epoch.
+ The recommendation is for these fields, along with ubik_epochTime, to
+ be additionally protected by a second lock, allowing the beacon
+ thread to examine them without holding the database lock; see the
+ section on the BEACON package for details.
+
+ The condition variable 'version_cond' is used to signal to that the
+ database version may have changed; it is broadcast in udisk_commit(),
+ in SDISK_SendFile(), and from the recovery thread; it is monitored by
+ ubik_WaitVersion(), which can be called by an application to wait for
+ a database version change (this is not currently used in OpenAFS).
+ This CV is associated with the database lock. When LWP is used, this
+ condition is signalled on &ubik_dbase->version.
+
+ The condition variable 'flags_cond' is used by udisk_end() to signal
+ that DBWRITING flag has been cleared. This wakes threads waiting in
+ ubik.c:BeginTrans() to begin a new transaction. This CV is
+ associated with the database lock. When LWP is used, this condition
+ is signalled on &ubik_dbase->flags.
+
+ When LWP is used, signals are also sometimes sent on &urecovery_state
+ and on &ubik_amSyncSite. However, nothing ever waits on these, and
+ no corresponding condition variables exist when pthreads is used.
+
+ The 'cachedVersion' field holds the database version represented by
+ the application's cache; this is compared against the current
+ database version to discover if the cache is up to date. Both
+ cachedVersion and the application cache itself are protected by
+ cache_lock, an AFS reader/writer lock.
+
+ When the application wishes to use the cache, it calls
+ ubik_CacheUpdate(), which verifies that the cache is current,
+ updating it if necessary (under a write lock), and then returns with
+ the application cache read-locked. The application can then rely on
+ the cache's contents not to change until it ends the transaction by
+ calling ubik_EndTrans() or ubik_AbortTrans(). When one of these
+ functions is called, the read lock is dropped, and a write lock may
+ be acquired temporarily to update both cachedVersion and the cache
+ (in the case of committing a write transaction) or to clear
+ cachedVersion, indicating the cache is invalid (in the case of
+ aborting a transaction).
+
+ In the case of ubik_EndTrans() on a write transaction, the cache is
+ held write-locked until udisk_commit() has completed; this is also
+ done in SDISK_Commit(), which insures that the contents of the
+ on-disk database and page cache cannot change while an active
+ transaction holds the cache lock. Note that both the recovery thread
+ and SDISK_SendFile() may replace the database contents wholesale;
+ however, these operations first abort all outstanding transactions.
+
+ Prior to the introduction of ubik_BeginTransReadAnyWrite(), an
+ application could choose to manage its own cache, updating it during
+ write transactions and when, at the beginning of a read transaction,
+ it was discovered to be out of date (due to a write done by another
+ server). Under this model, the application uses Ubik transaction
+ locks to protect not only the database but also its cache. However,
+ the use of ubik_BeginTransReadAnyWrite() allows some transactions to
+ proceed and read the database without acquiring any locks, which
+ makes it unsafe to depend on Ubik transaction locks to protect the
+ application cache. Applications which make use of this mode must set
+ ubik_SyncWriterCacheProc to point to a procedure to be called to
+ update the cache during ubik_EndTrans(), after udisk_commit() has
+ succeeded and before the cache_lock is released. These applications
+ must then refrain from ever updating the cache other than during that
+ procedure or during the callback passed to ubik_CheckCache().
+
+
+ struct ubik_trans - active transaction
+
+ This structure represents the state of an active transaction,
+ including transaction metadata and state and a list of all changes
+ made as part of the transaction.
+
+ Transactions are organized into a linked list referenced by the
+ corresponding database structure, protected by the database lock.
+ Each transaction contains an upward pointer to the database,
+ a transaction type, and a transaction ID, all of which are immutable
+ for as long as the transaction exists.
+
+ A transaction created via the REMOTE interface exists until ended by
+ a call to SDISK_Abort() or SDISK_ReleaseLocks() or aborted in
+ urecovery_CheckTid() due to a transaction ID mismatch or creation of
+ a new transaction (note that in this last case, cleanup will be
+ deferred if SDISK_Lock() is blocked on this transaction). In these
+ cases, ubik_currentTrans is cleared at the same time, under the
+ database lock, and further REMOTE calls will fail gracefully until
+ a new transaction is started. Thus, REMOTE transactions may be
+ considered valid only for as long as the database lock is held.
+
+ Transactions created via ubik_BeginTrans(), ubik_BeginTransReadAny(),
+ or ubik_BeginTransReadAnyWrite() exist until ended by a call to
+ ubik_AbortTrans() or ubik_EndTrans(). They are never destroyed from
+ within the UBIK package. Code which discovers a transaction by
+ traversing the database's active transaction list may access the
+ transaction only as long as the database lock is held, since once it
+ is released, an application thread may end the transaction.
+
+ Each transaction contains the following fields, which are protected
+ by the database lock:
+
+ + locktype - type of lock held by this transaction
+ + minCommitTime - unused
+ + seekFile - file number of database file pointer
+ + seekPos - position of database file pointer
+ + flags
+
+ File writes are represented by 'iovec_info', an XDR vector structure
+ (type iovec_wrt, a vector of struct ubik_iovec) containing the file,
+ position, and length of each write, and 'iovec_data', an XDR opaque
+ containing the corresponding data. These vectors and their contents
+ are protected by the database lock.
+
+ File truncations are represented by a linked list of struct
+ ubik_trunc, each of which contains a file number and the new size of
+ that file. This list, and the records contained in it, are protected
+ by the database lock.
+
+ While transactions are currently protected by the database lock, it
+ may be desirable in the future to introduce a per-transaction lock,
+ in order to facilitate increased concurrency.
+
+
+ struct ubik_server - server status
+
+ This structure is used to track the set of peer servers, including
+ state related to elections and recovery. The global 'ubik_servers'
+ points to a linked list of these structures, which is constructed
+ during initialization. Once the list has been constructed, no
+ entries are ever added or removed; in addition, the following fields
+ are not changed after startup:
+
+ + addr[0] - server's primary address
+ + magic - true if this is the magic server
+ + isClone - true if this server is a clone
+
+ The following fields are used by the BEACON package to track beacons
+ to this server and their results. Currently, they are sometimes
+ accessed under the database lock, and sometimes without benefit of
+ any lock. They should probably be protected by the same lock as
+ globals private to the BEACON package.
+
+ + lastVoteTime - last time this server voted yes for us
+ + lastBeaconSent - last time a beacon was sent to this server
+ + lastVote - true if its late vote response was yes
+ + up - true if this server is believed to be up
+ + beaconSinceDown - true if a beacon has successfully been sent to
+ this server since the last time it was down
+
+ The following fields are used by the RECOVERY package to track the
+ state of each server. They are also examined and modified by the
+ various ContactQuorum_* functions. Currently, they are sometimes
+ accessed under the database lock, and sometimes without benefit of
+ any lock. They should be fully protected by the database lock.
+
+ + version - server's database version
+ + currentDB - true if server's database is up-to-date
+
+ The addr[] array is used to track all known addresses for the remote
+ server; this list is used when attempting to contact a down server
+ via an alternate address, and to identify the source of incoming
+ server-to-server RPCs. The first element of this array is always the
+ primary address and does not change after initialization; other
+ elements are updated during initialization and when a remote server
+ calls DISK_UpdateInterfaceAddr().
+
+ The system normally maintains an active Rx connection to the VOTE and
+ DISK services on each server; pointers to these are kept in the
+ 'vote_rxcid' and 'disk_rxcid' fields.
+
+ Currently, the addr[] array, 'vote_rxcid', and 'disk_rxcid' are not
+ protected by any lock. Because these are shared among a number of
+ subsystems and it is usually desirable to avoid blocking on the
+ database lock when making RPCs, it is recommended to introduce a new
+ lock (the "server address lock") to protect these fields and the
+ globals 'ubikSecClass' and 'ubikSecIndex', which contain the security
+ classes used for setting up such connections. The new lock would
+ need to be held in the following cases:
+ + Before beginning any RPC using 'vote_rxcid' or 'disk_rxcid', for
+ the time it takes to call rx_GetConnection() or rx_NewCall()
+ + For the duration of ubikGetPrimaryInterfaceAddr()
+ + In ubeacon_Interact(), when building the set of connections to be
+ used for multi_VOTE_Beacon().
+ + In updateUbikNetworkAddress(), first while constructing the set of
+ connections to be used for multi_DISK_UpdateInterfaceAddr(), and
+ then again each time a server's list of addresses is updated.
+ However, the lock must NOT be held while waiting for the RPC to
+ complete, to avoid deadlock when multiple servers are starting at
+ the same time.
+ + For the duration of SDISK_UpdateInterfaceAddr()
+ + For the duration of ubeacon_ReinitServer(), with the optional
+ exception of the call to afsconf_UpToDate().
+ + In src/ubik/recovery.c:DoProbe(), first while constructing the set
+ of connections to be used for multi_DISK_Probe() and, if the probe
+ is successful, again while destroying the old connections for the
+ server under test and replacing them with new ones. See the
+ section on the RECOVERY package for additional notes.
+
+
+GLOBAL VARIABLES
+
+ The library has an unfortunate number of global variables which are not
+ part of any data structure. Nonetheless, some of these are
+ database-specific; see MULTI-DATABASE SUPPORT, below.
+
+ Globals private to a particular subsystem are discussed in the
+ description of that subsystem. This section discusses global variables
+ which are shared and/or part of external interfaces.
+
+ The following globals are used to convey configuration parameters from
+ the application to the Ubik library, and are intended to be set before
+ the first call to ubik_ServerInit(). They are not modified by Ubik, and
+ are not protected by locks:
+
+ + ubik_debugFlag - print debug messages (unused)
+ + ubikPrimaryAddrOnly - use only primary interface
+ + ubik_nBuffers - number of DISK package page cache buffers
+ + ubik_SRXSecurityProc - callback to create server security class
+ + ubik_SRXSecurityRock - argument for ubik_SRXSecurityProc
+ + ubik_CRXSecurityProc - callback to create client security class
+ + ubik_CRXSecurityRock - argument for ubik_CRXSecurityProc
+ + ubik_SyncWriterCacheProc - callback to update application cache
+ + ubik_CheckRXSecurityProc - callback to check if caller is OK
+ + ubik_CheckRXSecurityRock - argument for ubik_CheckRXSecurityProc
+
+ The following globals contain values which are computed during Ubik
+ initialization and not modified thereafter. They are not protected by
+ any lock, which is safe so long as suitable memory barriers exist across
+ creation of threads and Rx services (see the notes on initialization in
+ the UBIK package section). Note that some of these values are
+ database-specific and properly belong in the ubik_dbase structure:
+
+ + ubik_servers - linked list of servers (see above)
+ + amIClone - true if this server is a clone
+ + ubik_callPortal - UDP port used for server-to-server RPCs
+ + ubik_quorum - number of servers to make a quorum
+ + ubik_dbase - pointer to the (only) database (see above)
+ + ubik_host[] - array of local addresses
+ + ubik_sc[] - security classes for Ubik RPC services
+
+ The following globals are currently protected by the database lock,
+ though in most cases there are existing references which do not hold the
+ lock. Later sections of this document contain recommendations in each
+ case to establish new locks to protect these or to correct cases where
+ they are accessed without the correct lock.
+
+ + ubik_currentTrans - pointer to REMOTE's current transaction
+ + ubik_epochTime - epoch for transaction IDs
+ + urecovery_state - recovery state bits
+ + ubik_dbVersion - sync site's database version
+ + ubik_dbTid - sync site's transaction ID
+ + ubikSecIndex - security class index for making Ubik RPCs
+ + ubikSecClass - security class for making Ubik RPCs
+
+ The global 'ubik_amSyncSite' belongs to the BEACON package, and should
+ be protected by the same lock as that package's private globals. In
+ fact, it should probably be made private; the only references outside
+ BEACON are in SVOTE_Debug() and SVOTE_DebugOld() and can easily be moved
+ into ubeacon_Debug().
+
+
+MAJOR SUBSYSTEMS
+
+ This section describes each of the major Ubik server subsystems. For
+ each subsystem, a brief overview is provided, along with a description
+ of that subsystem's handling of synchronization (or lack thereof).
+ Subsystems are described beginning with the lowest layer and working
+ toward the highest.
+
+ PHYS - Physical I/O
+
+ This package is responsible for handling I/O to database files. It
+ maintains a private, global array of MAXFDCACHE(4) fdcache
+ structures, each representing an open file descriptor on a database
+ file, either presently in use or idle and available for use. Entries
+ are indexed by database file ID, and each contain a file descriptor
+ number and a refcount. There is also a global 'inited' flag, and
+ a buffer used to construct pathnames when opening database files.
+
+ The static function uphys_open() takes a database pointer and fileid
+ and attempts to open the corresponding file. On success, it returns
+ a file descriptor; on failure, it returns the same as open(2) (with
+ errno set). This prefers to reuse an already-open fd whose cache
+ refcount is 0; failing that, it opens a new fd and attempts to enter
+ it in the cache. It prefers first to use an unused cache entry, then
+ to reclaim an idle one whose refcount is 0; if neither is possible,
+ the newly-opened fd is returned without caching. Note that the
+ refcount on an active entry is always exactly 1; the same entry
+ cannot be referenced more than once.
+
+ The function uphys_close() releases a file descriptor opened by
+ uphys_open(). If the file descriptor was cached, the cache entry is
+ dereferenced but the file is left open for future use; 0 is returned.
+ If the file descriptor is not found in the cache, then the return
+ value is that of an immediate call to close(2). This function also
+ handles cleanup when a cached fd is closed after the file to which it
+ refers is invalidated by uphys_invalidate(). This function is not
+ static, but may as well be -- it is used only by other functions in
+ the PHYS package.
+
+ Functions in this package are called via method pointers in the
+ database structure, which are set during initialization and not
+ changed thereafter. These functions must be called with the database
+ lock held; this protects the file descriptor cache and other globals
+ mentioned above, and prevents conflicting access to database files.
+
+ The requirement that functions in this package be called with the
+ database lock held means that concurrent access to database files is
+ not possible. This situation could be improved by the addition of
+ a new global lock, which would be held for most of the duration of
+ uphys_open(), uphys_close(), and uphys_invalidate(), but need _not_
+ be held during actual file accesses. This would eliminate the
+ requirement that calls to this package be made with the database lock
+ held, allowing multiple calls to be active concurrently. However, it
+ would still be necessary for higher layers to employ appropriate
+ synchronization as needed to maintain database consistency.
+
+
+ DISK - Logical Database I/O and Transaction Management
+
+ This package is responsible for logical database file I/O, logging,
+ and transaction management. It maintains a private cache of database
+ file page buffers. This entire cache, including buffer space, is
+ allocated and initialized the first time a transaction is started;
+ the global initd flag keeps track of whether or not this has been
+ done. The size of this cache defaults to 20 pages, but may be
+ overridden by setting the global 'ubik_nBuffers' (all OpenAFS Ubik
+ services do this); this global is not protected by any lock, but is
+ read exactly once, when the cache is initialized.
+
+ Except for udisk_Debug() (see below), all udisk_* interfaces require
+ a pointer either to the database or to an active transaction, and
+ must be called with the database lock held. This protects the DISK
+ package's accesses of the active transaction list and associated
+ state variables as well as its calls into the physical access layer,
+ including insuring that operations requiring multiple calls into that
+ layer are performed atomically.
+
+ In addition, the database lock protects the page cache hash table and
+ LRU queue, the buffer control structures, buffer contents, the
+ truncation record free list (freeTruncList), and global statistics.
+ However, it may be desirable in the future to introduce a separate
+ lock to protect these structures, in order to facilitate multiple
+ database support.
+
+ udisk_LogOpcode, udisk_LogEnd, udisk_LogTruncate, udisk_LogWriteData
+
+ These are internal interfaces for writing to the transaction log.
+ They each construct a log record and then directly call the
+ physical layer to append it to the log; the log file is _not_
+ cached by the page buffer cache, and these functions do not touch
+ the cache. Each of these must be atomic with respect to other
+ writes to the log file, which is accomplished by insuring they are
+ called only with the database locked.
+
+ DInit, DRead, DTrunc, DRelease, DFlush, DAbort, DSync, DNew
+
+ These are internal interfaces for accessing the page buffer cache.
+ They must be called with the database lock held.
+
+ DRead() and DNew() return a pointer to the page data buffer, not
+ to the buffer control structure; this pointer is later passed to
+ DRelease() to release the buffer. This mechanism depends on the
+ fact that buffer control structures are allocated in the same
+ order as the actual page data buffers.
+
+ DRead() guarantees that a read transaction will always see a clean
+ copy of the requested page, without any modifications made by an
+ in-progress write transaction. However, this is true only if the
+ next layer insures that once DRead() is called with write intent
+ on a page, that no further calls to DRead() are made for that page
+ until the buffer is written and DRelease() is called with the
+ dirty flag. Presently, this is the case because udisk_read() and
+ udisk_write(), which are the only callers of DRead(), are both
+ called with the database lock held.
+
+ udisk_read, udisk_truncate, udisk_write, udisk_begin, udisk_commit,
+ udisk_abort, udisk_end, udisk_Invalidate
+
+ These are external interfaces provided by the DISK package to
+ higher layers. Presently, the locking requirements of these
+ functions and the lower-layer functions they call are satisfied by
+ the simple rule that these must always be called with the database
+ lock. In the future, support for multiple databases and/or
+ a greater level of concurrency may require relaxing this rule
+ and/or acquiring additional locks within these functions.
+
+ In udisk_commit(), when committing the first write transaction
+ after becoming sync site, the database is relabelled. In this
+ case, the UBIK_RECLABELDB recovery state bit should be set before
+ propagating the label change to other servers, rather than after.
+ This is because because ContactQuorum_DISK_Setversion() will
+ release the database lock, at which point the recovery state may
+ be cleared by urecovery_ResetState() running in another thread.
+ It is important that a relabelling which occurs before recovery
+ state is cleared not result in the UBIK_RECLABELDB recovery state
+ bit being set after; otherwise, the server may fail to correctly
+ relabel the database the next time it becomes sync site.
+
+ udisk_Debug
+
+ The udisk_Debug() interface is called as part of preparing the
+ response to Ubik debugging requests. Unlike other udisk_* APIs,
+ this interface is not called on a specific database and does not
+ require the database lock to be held. It reports the version data
+ of the single database identified by the global 'ubik_dbase' and
+ traverses the buffer cache collecting statistics, both without
+ benefit of holding any locks. This may produce inconsistent data
+ but does not normally risk damaging data structures or accessing
+ invalid or uninitialized memory (but see below), and avoiding
+ locking may be of greater benefit than guaranteeing the return of
+ consistent data.
+
+ The global 'ubik_dbase' pointer is set when the first (only)
+ database is initialized, and the buffer cache data structures are
+ allocated the first time a transaction is started, either locally
+ or via the REMOTE package. Once set, the pointers used by
+ udisk_Debug() are never changed, and the data structures they
+ point to remain valid and are never freed. The buffer cache is
+ traversed by iterating over the array of buffer cache elements
+ (this is done in other places as well), not by following a linked
+ list or other data structure that may reordered, and so should not
+ be dangerous.
+
+ At a minimum, then, it should be arranged that udisk_Debug()
+ cannot be called before the database structure and page cache have
+ been initialized. This means that both of these actions must be
+ taken before any incoming RPCs are accepted. Practically, this
+ means that DInit() should be renamed udisk_init(), and called from
+ ubik_ServerInitCommon() during initialization.
+
+ Full correctness demands that udisk_Debug actually hold the
+ database lock while copying the database version and examining the
+ page cache. However, it may be desirable to sacrifice this
+ correctness in order to reduce interaction between the debugging
+ interfaces and the rest of the system.
+
+ Helper functions:
+ + unthread - remove transaction from activeTrans
+ + Dlru, Dmru - move page to front/end of LRUQ
+ + MatchBuffer - check if a buffer's dbase/file/page match
+ + FixupBucket - move page to the right bucket
+ + newslot - find and allocate an unused buffer
+ + DedupBuffer - throw away stale copies after page is flushed
+ + GetTrunc, PutTrunc - trunc record allocation
+ + FindTrunc - find active trunc record for file
+ + DoTruncs - apply truncations
+
+
+ LOCK - Database Transaction Locking
+
+ This package is responsible for managing database locks held as part
+ of a transaction. It supports a single read/write lock, which is
+ represented by the global variable 'rwlock', a struct Lock. The
+ global 'rwlockinit' records whether Lock_Init() has been called on
+ this lock, and is protected by the database lock. Properly, this
+ lock should be treated as belonging to the database.
+
+ ulock_getLock() expects to be called with the database lock held; it
+ depends on this to protect access to fields within the transaction
+ structure as well as to the global 'rwlockinit'. However, note that
+ the database lock must be temporarily released while obtaining the
+ read/write lock, and so ulock_getLock() should not be called in the
+ middle of a critical section. The 'await' parameter may in theory be
+ set to 0 to effect a non-blocking lock; however, this depends on
+ (incorrect) knowledge of the internals of struct Lock. Fortunately,
+ existing Ubik code always sets await=1. This feature should be fixed
+ or removed.
+
+ ulock_relLock() releases the read/write lock. It expects to be
+ called with the database lock held. Unlock ulock_getLock(), this
+ function does not release the database lock.
+
+ ulock_Debug() reports the state of the read/write lock, for debugging
+ purposes. It depends on knowledge of the internals of struct Lock,
+ and accesses both the Lock structure and the global rwlockinit
+ without benefit of holding any lock.
+
+ It would probably be best to eliminate 'rwlockinit' in favor of
+ always initializing the global 'rwlock' during startup; ulock_Debug()
+ would then have no need to examine the flag. Further, ulock_Debug()
+ should at a minimum use the appropriate locks when looking inside
+ struct Lock; ideally, knowledge of that structure's internals should
+ be abstracted into appropriate interfaces in src/lwp/lock.[ch].
+
+
+ VOTE - Voting Logic and VOTE_* RPCs
+
+ This package is responsible for keeping track of who is currently
+ sync site and deciding how to vote and whether this server should try
+ to become sync site. It provides the VOTE RPC package, which is
+ primarily responsible for processing vote requests from peer servers
+ (VOTE_Beacon), but also provides debugging interfaces and an
+ interface (VOTE_GetSyncSite) to allow clients to discover the current
+ sync site.
+
+ Voting decisions are made using state tracked in a set of global
+ variables, listed below. Currently there is no locking protecting
+ these variables; LWP-based Ubik depends on the cooperative nature of
+ LWP and on the fact that routines which examine and manipulate them
+ do not block. Introduction of a new "vote lock" is recommended to
+ protect the following globals:
+
+ + ubik_lastYesTime - last time VOTE_Beacon voted "yes"
+ + lastYesHost - host voted for at ubik_lastYesTime
+ + lastYesClaim - time lastYesHost started its voting cycle
+ + lastYesState - whether lastYesHost claimed to be sync site
+ + lowestHost - lowest host seen
+ + lowestTime - last time lowestHost was updated/heard from
+ + syncHost - sync host, or 0 if none known
+ + syncTime - last time syncHost was updated
+ + ubik_dbVersion - sync site's database version
+ + ubik_dbTid - sync site's transaction ID
+
+ The vote lock should be initialized in uvote_Init() and held for the
+ remainder of that function and also during of uvote_ShouldIRun(),
+ uvote_GetSyncSite(). It should also be held for the bulk of
+ SVOTE_Beacon() -- specifically, it should be acquired just before
+ beginning the lowest-host calculation, and released just before
+ calling urecovery_CheckTid(), in the event of a yes vote or else just
+ before returning.
+
+ In addition, the vote lock would protect the globals 'ubik_dbVersion'
+ and 'ubik_dbTid', which represent this server's knowledge of the
+ state of the database on the sync site. This variable is set in two
+ places in the REMOTE package, which change the local and sync site
+ database versions at the same time. It is also examined in one place
+ in the REMOTE package, and compared to the database version in the
+ RECOVERY package. It is imperative that when the local and remote
+ versions are changed at the same time, these changes become visible
+ to the RECOVERY package at the same time. Thus, both the changes and
+ the comparison must be done under both locks. For this purpose,
+ three new functions should be provided by the VOTE package:
+
+ + A function to safely set 'ubik_dbVersion'
+ + A function to compare 'ubik_dbVersion' to another value
+ + A function to check whether this is sync site and compare
+ 'ubik_dbVersion' to another value, without releasing the vote lock
+ in between (to be used in recovery).
+
+ Existing accesses to 'ubik_dbVersion' in REMOTE and RECOVERY, all of
+ which are already made under the database lock, would be replaced
+ with calls to the new accessors.
+
+ The result of these changes will require in several places that the
+ vote lock be acquired while the database lock is already held.
+ Therefore, the vote lock MUST NOT be held while acquiring the
+ database lock.
+
+ SVOTE_Beacon() currently calls urecovery_CheckTid() without benefit
+ of the database lock, which must be held when calling that function.
+ This is fairly simple to fix; however, the vote lock must be released
+ first. One simple approach would be to move the call to
+ urecovery_CheckTid() to after the point where the vote lock will be
+ released, wrapping it in DBHOLD/DBRELE, and conditionalizing the
+ whole thing on 'vote' being nonzero.
+
+ Separately, it may be worth examining whether it is appropriate to
+ call urecovery_CheckTid() only when voting yes, and not whenever
+ a beacon is received from a server claiming to be sync site.
+
+ As with the debug functions in other packages, SVOTE_Debug() and
+ SVOTE_DebugOld() access global variables belong to this and other
+ modules without benefit of the appropriate locks. There is also very
+ little abstraction here. It is probably desirable to introduce Debug
+ interfaces for the VOTE and RECOVERY packages, to be called from
+ these functions. Full correctness requires...
+
+ + Holding the vote lock while accessing the VOTE package globals
+ described above.
+ + Holding the database lock while accessing the database flags and
+ tidCounter, ubik_epochTime, ubik_currentTrans, and urecovery_state
+
+
+ BEACON - elections, tracking whether this is sync site
+
+ This package is responsible for running elections, collecting votes,
+ and deciding whether and for how long this is the sync site. It also
+ contains routines responsible for setting up the list of servers and
+ acquiring alternate addresses for other servers during startup.
+
+ For this purpose, it maintains a number of global variables and
+ ubik_server structure fields. Currently, these variables and fields
+ are sometimes accessed under the database lock, and sometimes without
+ benefit of any lock. In order to allow this package to operate with
+ a minimum of disruption due to database accesses, it is recommended
+ that a new lock be established to protect these. It is particularly
+ desirable to prevent loss of sync due to the potentially long-lived
+ RPCs the RECOVERY package must make under the database lock when
+ transferring full database copies between servers; for this reason,
+ it is important that both the BEACON thread and SVOTE_Beacon() be
+ able to operate without acquiring the database lock. The global
+ variables and ubik_server structure fields to be protected by the new
+ lock are the following:
+
+ + ubik_amSyncSite - true if this is the sync site
+ + syncSiteUntil - time until which this is the sync site
+ + ts->lastVoteTime - last time this server voted yes for us
+ + ts->lastBeaconSent - last time a beacon was sent to this server
+ + ts->lastVote - true if its late vote response was yes
+ + ts->up - true if this server is believed to be up
+ + ts->beaconSinceDown - true if a beacon has successfully been sent
+ to this server since the last time it was down
+
+ The new lock would need to be held in the following cases:
+ + In ubeacon_AmSyncSite(), from the first time 'ubik_amSyncSite' is
+ examined until after the potential call to urecovery_ResetState().
+ + In ubeacon_Interact(), when building the list of servers to which
+ to send beacons (to protect access to the 'up' flag). Note that
+ the server address lock must also be held during this loop, and
+ must be acquired _after_ the beacon lock.
+ + In ubeacon_Interact(), when updating status associated with
+ a server after receiving its beacon response.
+ + In ubeacon_Interact(), when updating globals after an election.
+ However, it must be released before calling urecovery_ResetState().
+ + In updateUbikNetworkAddress(), when marking a server down.
+ + In the various ContactQuorum_* functions, when checking whether
+ a server is up before calling it, and again when marking a server
+ down after a call fails.
+ + In ubik_EndTrans, when examining a server's 'beaconSinceDown' flag
+ and 'lastBeaconSent' timestamp to determine whether it has recently
+ gone down, requiring a brief hold until it either comes back up or
+ times out.
+
+ The following global variables are set during initialization and do
+ not change thereafter:
+
+ + nServers - number of voting servers
+ + amIMagic - true if this server gets the extra half vote
+ + ubik_singleServer - true if this is the only server
+
+ Currently, all initialization of this module is done _after_ the Rx
+ services have been created and an Rx server thread started. This is
+ done to avoid a situation in which all servers are blocked in
+ updateUbikNetworkAddress(), which is responsible for exchanging
+ addresses with peer servers, while none of them is prepared to
+ handled the DISK_UpdateInterfaceAddr call made by that function.
+
+ When using LWP, this early initialization of Rx is not a problem,
+ because the various initialization routines don't actually block until
+ updateUbikNetworkAddress() waits for RPCs to complete. However, when
+ using pthreads, it is a problem, because it means that incoming RPCs
+ may be processed when initialization is not complete.
+
+ To address this problem and insure orderly initialization, it is
+ recommended to change the initialization sequence so that most work,
+ including the bulk of BEACON package initialization, happens before
+ Ubik's Rx services have been created. The only work that should be
+ deferred until after that point is updateUbikNetworkAddress(),
+ followed by starting the long-running threads belonging to the BEACON
+ and RECOVERY packages. This requires updateUbikNetworkAddress() to
+ be exported (and perhaps to undergo a name change).
+
+ The major part of the work of this package is done in the function
+ ubeacon_Interact(), which is the body of a long-running thread known
+ as the beacon thread. This thread is responsible for periodically
+ sending "beacons" to other servers to request votes (when the sending
+ server is the sync site, these also include how long it will remain
+ so, the database version, and the active transaction ID). Beacons
+ are sent only from servers that are already sync site or believe they
+ are the best candidate, as determined by uvote_ShouldIRun().
+
+ On the sync site, the beacon thread is responsible for insuring that
+ new votes are collected frequently enough to avoid loss of quorum.
+ This means it must not block for an extended time; therefore, it must
+ not acquire the database lock, which in other threads may sometimes
+ be held during long-running operations (most notably, database file
+ transfers done under this lock by the recovery thread). Instead,
+ a new lock is proposed (the "version lock"), which is used to allow
+ the beacon thread to examine (but not modify) certain fields without
+ holding the database lock.
+
+ The version lock should be acquired _in addition to_ the database
+ lock when modifying 'ubik_epochTime' or the database 'version',
+ 'flags', 'tidCounter', and 'writeTidCounter' fields; such
+ modifications occur at the following locations:
+ + in ubik.c:BeginTrans(), when beginning a new transaction
+ + in udisk_begin(), when setting DBWRITING
+ + in udisk_commit(), when updating the database version at the end of
+ a write transaction (note this includes the case of relabelling the
+ database on the first write transaction after becoming sync site)
+ + in udisk_end(), when clearing DBWRITING
+ + in recovery.c:InitializeDB(), when setting the initial version of
+ an empty database
+ + in urecovery_Interact(), when labelling a new database the first
+ time quorum is established
+ + in urecovery_Interact(), after fetching the latest database from
+ another server (whether successful or not; there are two cases)
+ + in SDISK_SendFile(), when updating the database version both before
+ and after receiving a new database from the sync site. Note the
+ lock must _not_ be held during the transfer.
+ + in SDISK_SetVersion()
+
+ The version lock should be acquired by the beacon thread while
+ examining these fields, shortly before calling multi_VOTE_Beacon().
+ Since it must release the lock before making that call, the database
+ version will need to be explicitly copied into a local variable, as
+ is already done with the current transaction ID.
+
+ Note that if UBIK_PAUSE is defined, the DBVOTING flag poses an
+ additional problem, as it must be modified by the beacon thread. If
+ it is desirable to continue to support this variant, then it becomes
+ necessary for all accesses to the database flags to be protected by
+ the version lock. Other UBIK_PAUSE code may not have been reviewed
+ in depth and may pose additional problems.
+
+ The function ubeacon_AmSyncSite() is called both from the beacon
+ thread and from various other points to determine whether they are
+ running on the sync site, and thus whether various operations are
+ safe and appropriate. Calls to this function from outside the beacon
+ thread (often, via urecovery_AllBetter()) must be made with the
+ database lock held, and for operations modifying the database or
+ relying on its contents to remain constant, this lock must not then
+ be released until the operation is complete. The does not guarantee
+ that this will remain sync site for the duration of the operation,
+ but does insure that any operations done after or as a result of
+ losing sync will in fact occur after the operation holding the lock.
+
+ Of course, ubeacon_Interact() itself cannot call ubeacon_AmSyncSite()
+ with the database lock held, since it must not block on that lock
+ when running on the sync site (otherwise sync could be lost, as
+ described above). So, that portion of ubeacon_AmSyncSite() other
+ than the call to urecovery_ResetState() should be abstracted out into
+ a new function, which presumably returns separate flags indicating
+ both whether it is in fact running on the sync site (which becomes
+ the return value of ubeacon_AmSyncSite()) and whether a call to
+ urecovery_ResetState() is indicated. When the latter is set, the
+ beacon thread can acquire the database lock (since, if this is not
+ the sync site, blocking on this lock is not a problem) and call
+ urecovery_ResetState().
+
+ This difference in behavior is acceptable because the required
+ invariant is that when 'ubik_amSyncSite' is cleared, it cannot become
+ true again until urecovery_state has also cleared. This insures that
+ once a server discovers it is not sync site, urecovery_AllBetter()
+ cannot succeed on the basis of being sync site until sync is regained
+ and recovery has run, insuring the database is up to date. Since
+ only the beacon thread ever sets 'ubik_amSyncSite' true, that thread
+ can meet the invariant by calling urecovery_ResetState() before doing
+ anything else, while other threads must continue to hold the beacon
+ lock to prevent the beacon thread from setting 'ubik_amSyncSite'.
+
+ ubeacon_Debug() reports the value of syncSiteUntil, without benefit
+ of obtaining any locks. It should also report the value of
+ 'ubik_amSyncSite', allowing that global to be made private to the
+ BEACON package. Full correctness requires that the beacon lock be
+ held while accessing these globals.
+
+
+ RECOVERY - Consistency, Down Server Recovery, Propagation, Log Replay
+
+ This package is responsible for tracking whether the local database
+ is current and usable and for discovering when a server comes back up
+ after having been marked down. On the sync site, it is also
+ responsible for tracking the database versions on remote servers and
+ for recovering from inconsistencies.
+
+ To carry out these tasks, the RECOVERY package maintains a single
+ global, 'urecovery_state'. This is not currently effectively
+ protected by any lock; however, it should be protected by the
+ database lock. This is particularly important because high-level
+ routines that manipulate the database depend on a check against this
+ field to determine that the database is up-to-date and safe to
+ modify, and that it will remain so until the operation is complete.
+
+ The main work of this package is done by urecovery_Interact(), which
+ is the body of a long-running thread known as the recovery thread.
+ This thread wakes up periodically to discover if any down servers
+ have come back up and, on the sync site, to locate the latest
+ available database, fetch it if necessary, and make sure it has been
+ distributed to all servers. This work is done in several steps,
+ taken on in sequence every few seconds:
+
+ + The first part of urecovery_Interact() is to identify servers which
+ are believed to be down, and determine whether any of them have
+ come back up. This is done every 30 seconds, even when this is not
+ the sync site. Currently, the database lock is held for the
+ duration of this loop, released only in DoProbe() while actually
+ waiting for the DISK_Probe() RPC to complete. This is mostly
+ unnecessary; the server probe loop needs this lock only to examine
+ the database 'currentDB' flag and to clear the UBIK_RECFOUNDDB bit,
+ and DoProbe() doesn't need it at all. However, the beacon lock is
+ needed to examine and update the database 'up' flag, and DoProbe()
+ needs to hold the server address lock when examining server
+ addresses and, if the server comes back up, to replace connections.
+ See the section on struct ubik_server for more details on this
+ lock.
+
+ + The next step is to determine whether this is the sync site, and
+ update the UBIK_RECSYNCSITE bit appropriately. The database lock
+ should be held for the duration of this step, as
+ ubeacon_AmSyncSite() may end up calling urecovery_ResetState(),
+ which requires that lock be held. If this is not the sync site,
+ the cycle ends here.
+
+ + Step three is to determine the location of the latest database.
+ This is done by making DISK_GetVersion() calls to all active
+ servers, keeping track of the newest version found and the server
+ which reported it. Once this is done, the best version is compared
+ to the local version, update the UBIK_RECHAVEDB bit (so that it is
+ true if and only if the local version is the latest) set the
+ UBIK_RECFOUNDDB bit to indicate the latest database has been
+ located, and clear the UBIK_RECSENTDB bit to force any servers with
+ out-of-date databases to be updated.
+
+ In this section, it is not necessary to hold any locks while
+ collecting versions on remote servers, though as before, it is
+ necessary to hold the beacon lock while examining the server 'up'
+ flag, and the address lock to obtain a reference on each connection
+ as it is used (but this lock should not be held during the RPC!).
+ Once all remote versions have been fetched, the database lock is
+ needed while examining the local version and updating
+ 'urecovery_state'. Note that write transactions may happen while
+ versions are collected, resulting in some servers having newer
+ versions than were detected. However, if this happens, the result
+ is always consistent and ends with the sync site having the latest,
+ canonical version:
+
+ + If the actual latest version X.N before the write was in an epoch
+ created by the current sync site, then that version must
+ necessarily already be present on the sync site, since writes are
+ always committed first on the sync site. Thus, when the sync
+ site updates the version counter, it produces a new version X.N+1
+ which no other server can believe it already has; thus, there is
+ no possibility of inconsistency.
+
+ + If the actual latest version X.N before the write was in an epoch
+ not created by the sync site, then it is possible that after
+ quorum was established but before any writes happened, a new
+ server came online which had a newer version X.N+1 (that was
+ committed to less than a quorum of sites before a crash). If
+ a write transaction begins before recovery detects this fact and
+ fetches the version X.N+1 database, then the new write will start
+ with the version X.N database, essentially creating a version
+ fork. However, when this happens, the resulting database will be
+ version Y.1 (with Y>X), because the first write on a new sync
+ site always results in a new database. Thus, the version X.N+1
+ database will no longer be latest (because the local version,
+ which is examined last, is Y.1), and will end up being discarded.
+ This is no worse than if the server with the version X.N+1
+ database had not come up until completely after the transaction
+ resulting in version Y.1.
+
+ + Step four is to fetch the latest database, if the sync site does
+ not already have it. Since this step replaces the database
+ wholesale, there can be no active transactions while it runs, and
+ all other database activity must be locked out for the duration of
+ the transfer. This means the database lock must be held for this
+ entire step, starting from the check that the UBIK_RECSYNCSITE
+ and/or UBIK_RECFOUNDDB bits are still set. (Note that the existing
+ comment which claims that it is impossible for UBIK_RECFOUNDDB not
+ to be set at this point is true only if the database is not
+ released since checking or updating that bit in step three). In
+ addition, the address lock must be held while setting up the call
+ to be used for DISK_GetFile().
+
+ + Step five, again after verifying that this is still the sync site
+ and that the UBIK_RECHAVEDB bit is set, is to distribute the new
+ database to any servers which do not already have it. Before this
+ can be done, if the database was newly-initialized (with label
+ epoch 1), it is relabeled with version 2.1 before it is distributed
+ to other sites. This allows readany transactions to run on such
+ a database (though probably not successfully, since the database is
+ empty); it is deferred until this point in recovery to insure that
+ if any server in the quorum contains a valid database, that version
+ is used rather than the empty one.
+
+ For this step, the database lock should be held starting at the
+ point at which the UBIK_RECSYNCSITE and/or UBIK_RECHAVEDB bits are
+ tested. In the event the DBWRITING flag is set, the lock must be
+ released while waiting for the active write transaction to end. In
+ this case, once the wait is completed, it is necessary to again
+ check urecovery_state to determine that this is still the sync site
+ and have an up-to-date database before proceeding.
+
+ It is probably simplest for urecovery_Interact() to acquire the
+ database lock at the start of step 2 described above, release it for
+ the duration of the version-collection part of step 3 and while
+ waiting for write transactions to terminate in step 5, and otherwise
+ hold it until the end of the cycle. If no work is needed, this means
+ the lock will be held relatively briefly; if it is necessary to fetch
+ and or send full database versions, these operations themselves must
+ be done with the lock held, and there is little point in releasing it
+ between them. However, it is acceptable to release the lock between
+ any steps described above, provided that each time the database lock
+ is released and reacquired, 'urecovery_state' is checked to verify
+ that no regression has occurred. Note that outside of the recovery
+ thread, the only changes that may occur to 'urecovery_state' are that
+ it may be completely cleared by urecovery_ResetState(), and that the
+ UBIK_RECLABELDB bit may be set by udisk_commit(), on the sync site.
+
+ The function urecovery_AllBetter() is called under the database lock
+ by routines which need to know whether there is a usable database.
+ As noted in the discussion of ubeacon_AmSyncSite() above, callers
+ must then continue to hold the database lock until any database
+ operation is complete. Further, callers which intend to write to the
+ database currently follow a call to urecovery_AllBetter() with a call
+ to ubeacon_AmSyncSite(), to determine whether a write is permissible.
+ Unfortunately, this is not safe, because it is possible (though
+ admittedly unlikely) for urecovery_AllBetter() to succeed on the
+ basis of being a non-sync-site with an up-to-date database, and then
+ for a subsequent call to ubeacon_AmSyncSite() to return a true result
+ (because the latter may block on acquiring the beacon lock, during
+ which time this may become the sync site). To insure that no write
+ operation is performed without an up-to-date, writeable database,
+ urecovery_AllBetter() should be modified to indicate whether a write
+ operation is permitted, which is the case only when UBIK_RECHAVEDB is
+ tested and found to be set.
+
+ The functions urecovery_AbortAll(), urecovery_CheckTid(), and
+ urecovery_ResetState() all expect to be called with the database lock
+ held.
+
+ The function urecovery_LostServer() need not be called with any
+ locks; it is merely a wrapper for ubeacon_ReinitServer().
+
+ The RECOVERY package is also responsible at startup for replaying the
+ transaction log and initializing an empty database. These tasks are
+ handled by urecovery_Initialize() and its helpers, ReplayLog() and
+ InitializeDB(). Because the helpers use PHYS package functions and
+ manipulate database structure fields, urecovery_Initialize() should
+ acquire the database lock before calling them.
+
+
+ REMOTE - remote database I/O (DISK) RPCs
+
+ This package provides the DISK RPC package, which mediates remote
+ access to the local database copy, when another server is sync site.
+ It also includes DISK_UpdateInterfaceAddr(), which is used during
+ initialization to verify consistency of configuration across servers,
+ and DISK_Probe(), which is used by the RECOVERY module to determine
+ whether the server is up.
+
+ As the functions in this package are RPC implementations, they may be
+ called at any time and are entirely responsible for their own
+ locking. There can be at most one active remote write transaction at
+ a time; this rule is enforced by this package, which maintains the
+ global 'ubik_currentTrans' as a pointer to the active transaction.
+
+ For the most part, the RPCs in this module use a common prologue,
+ which includes acquiring the database lock, and do not release that
+ lock until just before returning. However, the common prologue
+ examines both 'ubik_currentTrans' and the transaction flags without
+ benefit of the database lock. This can be corrected fairly easily by
+ acquiring the database lock sooner; however, this requires referring
+ to the database via the ubik_dbase global rather than via the 'dbase'
+ pointer in 'ubik_currentTrans'.
+
+ Note that SDISK_GetVersion() and SDISK_SetVersion() contain a sanity
+ check to ensure they are not running on the sync site, since these
+ are called only from that portion of the recovery loop which runs
+ only on the sync site. These calls to ubeacon_AmSyncSite() must be
+ made with the database lock held, for the results to be valid. The
+ same holds true for a commented-out check in SDISK_GetFile() (which
+ really should remain that way -- there's no reason not to allow any
+ authorized caller to do this at any time).
+
+ Additionally, note that SDISK_Commit() acquires a write lock on the
+ application cache, to insure that no transactions are running which
+ depend on the application cache, page cache, or underlying database
+ to change. The locking order requires that this lock be acquired
+ before taking the database lock; thus, both locks must be acquired
+ earlier.
+
+ SDISK_SendFile() is really quite bad in its handling of the database
+ lock under error conditions. Presently, an error condition may cause
+ it to release the lock too early nor not at all.
+
+ SDISK_UpdateInterfaceAddr() is called by peer servers as part of
+ their startup process, to trade lists of additional addresses and
+ insure sufficient agreement on configuration to allow the new server
+ to start. It will need to acquire the lock protecting the addr[]
+ array attached to each host.
+
+
+ UBIK (high-level API)
+
+ This package contains the high-level APIs exported by Ubik to
+ applications, including initialization, the APIs for creating and
+ using transactions, and various utilities. It also contains a number
+ of internal utilities.
+
+ Initialization
+
+ Initialization of Ubik is handled in ubik_ServerInitCommon(),
+ which is called by two API functions, ubik_ServerInit() and
+ ubik_ServerInitByInfo(), which provide different interfaces for
+ passing configuration information. This code handles
+ initialization of the database, locks, and various globals, calls
+ the initialization routines for each subsystem, makes sure Rx has
+ been initialized, and creates Ubik's Rx services and threads.
+
+ Most of this is done before any Ubik-specific threads are created
+ and before Ubik's RPCs can be called, and so takes place without
+ holding any lock. However, since Rx may have been initialized and
+ started before Ubik, it is possible that some Rx worker threads
+ may have already been created. In practice, locks internal to Rx
+ should insure that any memory writes made before an Rx service is
+ created become visible to any worker running on behalf of that
+ service; nonetheless, this should not be depended on, and proper
+ locking should be used during all phases of initialization.
+
+ Unfortunately, the current code actually starts Rx services before
+ initialization is complete, resulting in a number of possible
+ races. The general THREAD SAFETY section below contains
+ recommendations for reordering the startup process to eliminate
+ this problem, while still avoiding potential deadlock if multiple
+ servers start at once.
+
+ ContactQuorum_*
+
+ Nearly a third of ubik.c consists of various ContactQuorum_*
+ functions, which are used to make a particular RPC to every server
+ in the quorum. These used to be a single ContactQuorum()
+ function, but have been split into multiple functions to regain
+ type-safety. These retain a common prologue and epilogue, some
+ small part of which has been abstracted out, but most of which
+ remains duplicated in each of these functions. Indeed, the only
+ part unique to each function is the actual RPC call and, in the
+ case of ContactQuorum_DISK_WriteV(), code to fall back to multiple
+ calls to DISK_Write() on a per-server basis.
+
+ The code common to all ContactQuorum_* functions will need to
+ acquire the beacon lock when checking whether a server is up (no
+ calls are made to servers which are not marked up), and again when
+ marking a server down. Note that when a server is marked down,
+ the 'up' and 'beaconSinceDown' flags must be cleared at the same
+ time, without releasing the beacon lock. In addition, the helper
+ function Quorum_StartIO() must obtain the server address lock
+ while it obtains a reference on the Rx connection that will be
+ used.
+
+ All of the ContactQuorum_* functions must be called with the
+ database lock held; this is necessary to protect their access to
+ each server's 'version' and 'currentDB' fields and to the local
+ database version. However, these functions release the lock while
+ actually making RPCs. This behavior is new -- ContactQuorum() in
+ OpenAFS 1.4 did not release the database lock during RPCs -- but
+ it is safe, because no caller of ContactQuorum_*() depends on
+ state read under the database lock before the call to remain valid
+ after.
+
+ Transactions
+
+ The main Ubik transaction API consists of ubik_BeginTrans(),
+ ubik_BeginTransReadAny(), ubik_BeginTransReadAnyWrite(),
+ ubik_AbortTrans(), ubik_EndTrans(), ubik_Read(), ubik_Write(),
+ ubik_Flush(), ubik_Seek(), ubik_Tell(), ubik_Truncate(), and
+ ubik_SetLock(). The ubik_Begin* functions require a database
+ pointer; all others require an active transaction pointer. These
+ functions are called directly by the application without any
+ locks, and are responsible for their own locking. Note that many
+ of these examine the transaction type before acquiring any locks;
+ this is permissible because the transaction type is immutable once
+ the transaction is created (but it requires that the call be made
+ from the thread that created the transaction, or that the
+ application have used some mechanism to insure an appropriate
+ memory barrier exists; the same mechanism used to protect the
+ transaction pointer should suffice).
+
+ BeginTrans() contains the common code responsible for starting
+ a new transaction; this is made available to applications as
+ ubik_BeginTrans(), ubik_BeginTransReadAny(), and
+ ubik_BeginTransReadAnyWrite(). If a write transaction is in
+ progress, this function waits for it to complete. However, since
+ doing so releases the database lock, it is necessary to call
+ urecovery_AllBetter() again once the lock has been reacquired.
+ Further, in the UBIK_PAUSE case, the DBVOTING flag may have been
+ set, so this also must be retested (see the BEACON package section
+ for more on the difficulties of UBIK_PAUSE and DBVOTING).
+
+ Both ubik_Flush() and ubik_Write() examine and manipulate the
+ transaction I/O vector without benefit of any lock. These fields
+ ('iovec_info' and 'iovec_data') should be protected by the
+ database lock. In the case of ubik_Write(), this may require
+ releasing the lock before calling ubik_Flush(), or the
+ introduction of a private ubik_Flush_r() which assumes the lock is
+ already held (but note that in either case, the lock is released,
+ because ubik_Flush() calls ContactQuorum_* functions).
+
+ Utilities
+
+ The functions ubik_GetVersion() and ubik_WaitVersion() provide the
+ application with a way to discover the current database version
+ and to wait for it to change. These interfaces are not currently
+ used in OpenAFS. ubik_GetVersion() needs to acquire the database
+ lock while copying the database version.
+
+ The internal function ubikGetPrimaryInterfaceAddr() is used by
+ Ubik RPCs to determine a peer server's primary address, given the
+ IP address from which a call arrived. This needs to hold the
+ server address lock, as described in the section on struct
+ ubik_server.
+
+ Application Cache
+
+ The section on struct ubik_dbase describes the operation of the
+ application cache. The function ubik_CheckCache() is provided to
+ allow an application to insure the cache is up to date and obtain
+ a read lock on the cache which lasts for the duration of the
+ transaction.
+
+ Note that ubik_AbortTrans() currently always invalidates the
+ application cache by clearing ubik_dbase->cachedVersion, for which
+ it requires a write lock on the cache_lock. This means that
+ aborted transactions block waiting for completion of any
+ transactions which hold the cache_lock, which may well include all
+ outstanding transactions. In the case of read transactions, which
+ cannot have modified the database, this is unnecessary and may
+ significantly reduce concurrency.
+
+
+THREAD SAFETY
+
+ This section discusses changes needed to insure thread safety.
+
+ The initialization sequence in ubik_ServerInitCommon() should be cleaned
+ up, to ensure that every subsystem is fully initialized before starting
+ any background threads or accepting RPCs. The correct initialization
+ sequence should look something like this:
+
+ + Initialize error tables
+ + Allocate and initialize the database structure
+ + Initialize Rx
+ + Initialize the various subsystems:
+ + udisk_Init() (formerly disk.c:DInit)
+ + ulock_Init() (new, pulled out of ulock_getLock)
+ + uvote_Init()
+ + urecovery_Initialize()
+ + ubeacon_InitServerList*
+ + Create Rx services
+ + Start an Rx server thread
+ + updateUbikNetworkAddress() (rename and export from beacon.c)
+ + Start the beacon and recovery threads
+
+ Initialization functions may need to be added for some subsystems which
+ do not currently have them:
+
+ + src/ubik/disk.c:DInit() should be exported and renamed
+ udisk_Init(); it can then be called from ubik_ServerInitCommon()
+ instead of from udisk_begin().
+
+ + The lock initialization currently done in ulock_getLock() should
+ instead be done in a separate ulock_Init(), which should be called
+ from ubik_ServerInitCommon()
+
+ A new lock is needed to protect state belonging to the VOTE package,
+ including the globals 'ubik_dbVersion' and 'ubik_dbTid', which represent
+ the sync site's database state. See the VOTE package section for
+ details on the use of the vote lock.
+
+ A new lock is needed to protect state belonging to the BEACON package,
+ including the globals 'ubik_amSyncSite' and 'syncSiteUntil' and several
+ fields in the ubik_server structure. This lock also protects the
+ per-server 'up' flag, which is shared among several modules. In
+ addition, some beacon-specific fields are accessed directly by other
+ modules. Thus, this lock must be visible outside the BEACON module, or
+ else accessors must be provided for these items. See the BEACON package
+ section for details on the use of the beacon lock.
+
+ A new lock is needed to provide additional protection for the database
+ version, transaction counter, and flags, so that these can safely be
+ examined (but not updated) by the beacon thread without the need to
+ acquire the database lock. See the BEACON package section for details
+ on the use of the version lock.
+
+ A new lock is needed to protect per-server lists of non-primary
+ addresses, connections to the VOTE and DISK services on each server, and
+ the client-mode security class objects used to set up these connections.
+ See the section on struct ubik_server for details on the use of the
+ server address lock.
+
+ The required locking order is described by the following list. Any of
+ these locks may be acquired singly; when acquiring multiple locks, they
+ should be acquired in the listed order:
+
+ + application cache lock (dbase->cache_lock)
+ + database lock (DBHOLD/DBRELE)
+ + beacon lock
+ + vote lock
+ + version lock
+ + server address lock
+
+ Some cleanup is required in various places where existing locking
+ conventions are not properly obeyed:
+
+ + SVOTE_Beacon() needs to hold the database lock when calling
+ urecovery_CheckTid()
+
+ + Management of the database lock in SDISK_SendFile() needs to be
+ cleaned up so that it is always released at the proper time.
+
+ + urecovery_Interact() is not consistent about holding the database
+ lock when it examines and updates 'urecovery_state'. It also
+ examines the local database version at least once without benefit
+ of this lock. See the RECOVERY package section for details on
+ which locks are needed when by urecovery_Interact().
+
+ + ubik_Flush() and ubik_Write() need to acquire the database lock
+ before accessing the 'iovec_info' and 'iovec_data' fields.
+
+ + ubik_GetVersion() needs to acquire the database lock before copying
+ the database version.
+
+ The various debugging RPCs in the VOTE packages, and the data collection
+ routines they call in other packages, generally operate without benefit
+ of any locks. This is probably desirable, as it avoids any possibility
+ of debugging operations blocking on or interfering with the rest of the
+ system, and allows debugging data to be collected even in the event of
+ some unforeseen deadlock. It is also "safe", in that it does not risk
+ damage to data structures or access to uninitialized memory, provided
+ that data structure initialization is complete before these functions
+ are called. However, it does mean that these RPCs may return data that
+ is not entirely self-consistent.
+
+ + Correctness requires various locks be held during parts of
+ SVOTE_Debug() and SVOTE_DebugOld(); see the VOTE package section.
+
+ + SVOTE_Debug() also examines 'ubik_currentTrans' without benefit of
+ the database lock. This usage is not "safe", as that transaction
+ may be freed by another thread while SVOTE_Debug() is examining it.
+
+ + SVOTE_XSDebug() should hold the server address lock while copying
+ out server addresses, and other locks while copying per-server
+ state.
+
+ + udisk_Debug() should hold the database lock while examining the
+ database version and collecting page cache statistics.
+
+ + ulock_Debug should use LOCK_LOCK/LOCK_UNLOCK when examining the
+ internals of struct Lock. Ideally, knowledge of these internals
+ should be abstracted to src/lwp/lock.h.
+
+ + ubeacon_Debug() should hold the beacon lock while accessing the
+ value of 'syncSiteUntil' and, if the access is moved here from
+ SVOTE_Debug/SVOTE_DebugOld, 'ubik_amSyncSite'.
+
+CONCURRENCY THOUGHTS
+
+ This section collections information discussed previously about changes
+ that may be required or desirable in order to improve concurrency. Note
+ that none of these changes are needed to insure thread safety, provided
+ the changes discussed in the previous section are made.
+
+ + PHYS could be made more concurrent by maintaining a separate lock for
+ the fdcache, avoiding the need to DBHOLD while calling these.
+ However, higher-layer consistency probably requires that certain calls
+ or groups of calls to this package be atomic and isolated.
+
+ + Could DISK be made more concurrent by maintaining a separate lock for
+ the page cache and or free truncation record list?
+
+ + Could concurrency be improved by maintaining separate per-transaction
+ locks? If so, what is the locking hierarchy with respect to database
+ locks and the DISK and PHYS package locks?
+
+ + Could concurrency be improved by maintaining more reader/writer state
+ and/or separate write locks to insure consistency of database file
+ access without requiring so much DBHOLD?
+
+ + Alternately, could concurrency be improved by requiring that an active
+ transaction be accessed only by the thread that created it?
+
+
+MULTI-DATABASE SUPPORT
+
+ There isn't any. Some of the Ubik interfaces and even the organization
+ of some internal data structures makes it appear as though multiple
+ databases can be supported. However, this is not the case, for several
+ reasons:
+
+ + Only a single set of peer servers is tracked, via a global linked list
+ of server structures. Each server structure includes state such as
+ the server's database version and whether it is up-to-date, so it is
+ not possible to track multiple databases even for a common set of
+ servers.
+ + The physical I/O package (phys.c) tracks cached open file descriptors
+ without regard to what database a file is part of; thus, it cannot
+ handle accessing multiple databases at the same time.
+ + There are a variety of globals containing state which needs to be
+ tracked on a per-database basis.
+ + There are a variety of globals which are effectively protected by
+ a per-database lock, or by no lock at all.
+ + The various RPCs used to communicate between servers assume a single
+ database and do not include a database identifier. Thus, in the
+ presence of multiple databases, it would be impossible to determine,
+ for example, for which database a DISK RPC was intended.
+
+ The upshot of this is that considerable work would be needed to get Ubik
+ into a condition which would allow a single process to maintain multiple
+ independent Ubik databases at the same time. Note that this is
+ orthogonal to the question of whether a single multi-file database is
+ possible.
+
+
+OTHER DATA STRUCTURES
+
+ Some other data structures are mentioned in ubik.p.h or elsewhere, but
+ are of relatively little interest from the point of view of threading.
+ They are described here primarily as an alternative to deleting
+ descriptive text that was already written.
+
+ struct ubik_hdr - on-disk database file header
+
+ This structure represents the on-disk format of the Ubik database
+ file header (label). It is used only for local variables in
+ uphys_getlabel() and uphys_setlabel(), which read and write this
+ header, respectively.
+
+ struct ubik_stat - database file status
+
+ This structure is used to convey the size and modification timestamp
+ of a database file. It is used as the type of an output parameter of
+ uphys_stat(), and for local variables in callers of that function.
+
+ struct ubik_stats - global statistics
+
+ This structure is used to contain "miscellaneous" global statistics.
+ Currently that consists of a single counter which is incremented in
+ one place (an exceptional condition in ubik_EndTrans) and is never
+ read. The one increment is performed only when holding the database
+ lock; thus, this structure may be treated the same as other globals
+ protected by non-global locks.
+
+OTHER NOTES
+
+ There appears to be nothing to insure that calls to disk.c:DRead()
+ during a write transaction won't find and use a "clean" cached page when
+ there is already a dirty page in the cache resulting from an earlier
+ write as part of the same transaction. This means that if a transaction
+ reads a page after writing it, it may read back the original data
+ instead of the new, and if a transaction writes a page more than once,
+ the later writes may corrupt the database. It seems likely that we are
+ merely lucky in this regard, and this problem should be fixed.
+
+ src/ubik/beacon.c:ubeacon_ReinitServer() assumes 'ubik_CRXSecurityRock'
+ is in fact an AFS configuration directory pointer, suitable as an
+ argument to afsconf_UpToDate(). This is inappropriate;
+ 'ubik_CRXSecurityRock' is an opaque argument to
+ (*ubik_CRXSecurityProc)(), Ubik must not make assumptions about what it
+ is.
+
+ It may be worth examining whether it is appropriate for SVOTE_Beacon()
+ to call urecovery_CheckTid() only when voting yes, and not whenever
+ a beacon is received from a server claiming to be sync site.
+
+ Recently, code has been introduced which attempts to insure that the
+ recovery process does not truncate an old database file before a new one
+ has been fully transferred, since this could, depending on the timing of
+ a server failure, deprive the new quorum of a valid database. This
+ so-called "new recovery" code violates the abstraction provided by the
+ PHYS package, encoding specific knowledge of the underlying file store
+ into the REMOTE and RECOVERY packages. This means that the backend
+ provided by phys.c cannot be replaced with an alternative, since in that
+ case recovery would do the wrong thing with the transferred database.
+
+ The DBWRITING loop in urecovery_Interact() is not portable, as it
+ depends the contents of the timeout after a call to select(2). This was
+ fine for IOMGR_Select(), which has defined behavior, but not for
+ select(2).
+
git://git.openafs.org / openafs.git / commitdiff