Documentation Source Text

proc C_Code {text} {
  hd_puts "<pre>\n"
  set iLine 0
  foreach zLine [split [string trim $text "\n"] "\n"] {
    set zLine [string map {< &lt; > &gt;} $zLine]
    set zSubspec {<span style="color:blue;font-style:italic">&</span>}
    regsub {(/\*|^ *\*\*|\*/).*} $zLine $zSubspec zLine 
    if {[regexp {(.*)(sqlite3[a-z0-9_]*)(.*)} $zLine -> one two three]
      && $two ne "sqlite3_blocking_prepare_v2"
    } {
      hd_puts $one
      hd_resolve "\[$two\]"
      hd_puts $three
    } else {
      hd_puts $zLine
    }
    hd_puts "\n"

  are used to ensure that concurrently executing transactions are kept 
  isolated. Before writing to a table, a write (exclusive) lock must be 
  obtained on that table. Before reading, a read (shared) lock must be
  obtained. A connection releases all held table locks when it concludes
  its transaction. If a connection cannot obtain a required lock, then
  the call to [sqlite3_step()] returns SQLITE_LOCKED.

<p>
  Although it is less common, a call to [sqlite3_prepare()] or
  [sqlite3_prepare_v2()] may also return SQLITE_LOCKED if it cannot obtain
  a read-lock on the sqlite_master table of each attached database. These
  APIs need to read the schema data contained in the sqlite_master table
  in order to compile SQL statements to [sqlite3_stmt*] objects.

<p>
  This page presents a technique using the SQLite [sqlite3_unlock_notify()]
  API to create a versions of [sqlite3_step()] and [sqlite3_prepare_v2()] that 
  block until the required locks are available instead of returning 
  SQLITE_LOCKED immediately, for use in multi-threaded applications. If the
  sqlite3_blocking_step() or sqlite3_blocking_prepare_v2() functions presented 
  to the left return SQLITE_LOCKED, this indicates that to block would 
  deadlock the system.

<p>
  The [sqlite3_unlock_notify()] API, which is only available if the library is
  compiled with the pre-processor symbol [SQLITE_ENABLE_UNLOCK_NOTIFY] defined,
  is [sqlite3_unlock_notify | documented here]. This page is no substitute for
  reading the full API documentation!

<p><b>The sqlite3_unlock_notify() API</b>

<p>
  After a call to [sqlite3_step()] or [sqlite3_prepare_v2()] returns 
  SQLITE_LOCKED, the [sqlite3_unlock_notify()] API may be invoked to register 
  for an unlock-notify callback. The unlock-notify callback is invoked by 
  SQLite after the database connection holding the table-lock that prevented
  the call to [sqlite3_step()] or [sqlite3_prepare_v2()] from succeeding has
  finished its transaction and released all locks. For example, if a call to
  sqlite3_step() is an attempt to read from table X, and some other connection
  Y is holding a write-lock on table X, then sqlite3_step() will return
  SQLITE_LOCKED. If [sqlite3_unlock_notify()] is then called, the unlock-notify
  callback will be invoked after connection Y's transaction is concluded. The
  connection that the unlock-notify callback is waiting on, in this case
  connection Y, is known as the "blocking connection".

<p>
  If a call to sqlite3_step() that attempts to write to a database table
  returns SQLITE_LOCKED, then more than one other connection may be holding 
  a read-lock on the database table in question. In this case SQLite simply
  selects one of those other connections at random and issues the 
  unlock-notify callback when that connection's transaction is finished.

  The algorithm used by the sqlite3_blocking_step() function is as follows:

<ol>
  <li><p> Call sqlite3_step() on the supplied statement handle. If the call
       returns anything other than SQLITE_LOCKED, then return this value
       to the caller. Otherwise, continue.

  <li><p> Invoke [sqlite3_unlock_notify()] on the database connection handle
       associated with the supplied statement handle to register for an
       unlock-notify callback. If the call to unlock_notify() returns
       SQLITE_LOCKED, then return this value to the caller.

  <li><p> Block until the unlock-notify callback is invoked by another thread.

  <li><p> Call sqlite3_reset() on the statement handle. Since an 
       SQLITE_LOCKED error may only occur on the first call to sqlite3_step()
       (it is not possible for one call to sqlite3_step() to return 
       SQLITE_ROW and then the next SQLITE_LOCKED), the statement handle may 
       be reset at this point without affecting the results of the query
       from the point of view of the caller. If sqlite3_reset() were not
       called at this point, the next call to sqlite3_step() would return
       SQLITE_MISUSE.

  <li><p> Return to step 1.

<p>
  The algorithm used by the sqlite3_blocking_prepare_v2() function is similar,
  except that step 4 (reseting the statement handle) is omitted.

</ol>

<p><b>Writer Starvation</b>

<p>
  Based on the description above, it could be concluded that if there are
  sufficient database readers reading the same table often enough, it is

<ul>
  <li> The current writer concludes its transaction, OR
  <li> The number of open read-transactions on the shared-cache drops to zero.
</ul>

<p>
  Failed attempts to open new read-transactions return SQLITE_LOCKED to the
  caller. If the caller then calls [sqlite3_unlock_notify()] to register for
  an unlock-notify callback, the blocking connection is the connection that
  currently has an open write-transaction on the shared-cache. This prevents
  writer-starvation as, if no new read-transactions may be opened and 
  assuming all existing read-transactions are eventually concluded, the 
  writer will eventually have an opportunity to obtain the required
  write-lock.

<p><b>The pthreads API</b>

  <p> By the time [sqlite3_unlock_notify()] is invoked by
      wait_for_unlock_notify(), it is possible that the blocking connection
      that prevented the sqlite3_step() or sqlite3_prepare_v2() call from 
      succeeding has already finished its transaction. In this case, the 
      unlock-notify callback is invoked immediately, before 
      [sqlite3_unlock_notify()] returns. Or, it is possible that the 
      unlock-notify callback is invoked by a second thread after 
      [sqlite3_unlock_notify()] is called but before the thread starts waiting 
      to be asynchronously signalled. 

  <p> Exactly how such a potential race-condition is handled depends on the
      threads and synchronization primitives interface used by the application.
      This example uses pthreads, the interface provided by modern UNIX-like 
      systems, including Linux.

  <p> The pthreads interface provides the pthread_cond_wait() function. 
      This function allows the caller to simultaneously release a mutex
      and start waiting for an asynchronous signal. Using this function,
      a "fired" flag and a mutex, the race-condition described above may
      be eliminated as follows:

  <p> When the unlock-notify callback is invoked, which may be before the
      thread that called [sqlite3_unlock_notify()] begins waiting for the 
      asynchronous signal, it does the following:

    <ol>
      <li> Obtains the mutex.
      <li> Sets the "fired" flag to true.
      <li> Attempts to signal a waiting thread.
      <li> Releases the mutex.
    </ol>

  <p> When the wait_for_unlock_notify() thread is ready to begin waiting for
      the unlock-notify callback to arrive, it:

    <ol>
      <li> Obtains the mutex.
      <li> Checks if the "fired" flag has been set. If so, the unlock-notify
           callback has already been invoked. Release the mutex and continue.
      <li> Atomicly releases the mutex and begins waiting for the
           asynchronous signal. When the signal arrives, continue.
    </ol>

  <p> This way, it doesn't matter if the unlock-notify callback has already
      been invoked, or is being invoked, when the wait_for_unlock_notify() 
      thread begins blocking.

<p><b>Possible Enhancements</b>

  <p> The code on this page could be improved in at least two ways:

  <ul>
    <li> It could manage thread priorities.
    <li> It could handle a special case of SQLITE_LOCKED that can occur
         when dropping a table or index.
  </ul>

  <p>
    Even though the [sqlite3_unlock_notify()] function only allows the caller
    to specify a single user-context pointer, an unlock-notify callback 
    is passed an array of such context pointers. This is because if when
    a blocking connection concludes its transaction, if there is more
    than one unlock-notify registered to call the same C function, the
    context-pointers are marshalled into an array and a single callback
    issued. If each thread were assigned a priority, then instead of just
    signalling the threads in arbitrary order as this implementation does,
    higher priority threads could be signalled before lower priority threads.

  <p>
    If a "DROP TABLE" or "DROP INDEX" SQL command is executed, and the
    associated database connection currently has one or more actively
    executing SELECT statements, then SQLITE_LOCKED is returned. If
    [sqlite3_unlock_notify()] is called in this case, then the specified
    callback will be invoked immediately. Unless the other running SELECT 
    statements complete execution in the meantime, re-attempting the "DROP
    TABLE" or "DROP INDEX" statement will return another SQLITE_LOCKED 
    error. In the implementation of sqlite3_blocking_step() shown to the
    left, this could cause an infinite loop.

  <p>
    The caller could distinguish between this special "DROP TABLE|INDEX" 
    case and other cases by using extended error codes. When it is appropriate
    to call [sqlite3_unlock_notify()], the extended error code is
    SQLITE_LOCKED_SHAREDCACHE. Otherwise, in the "DROP TABLE|INDEX" case,
    it is just plain SQLITE_LOCKED. Another solution might be to limit
    the number of times that any single query could be reattempted (to say 
    100). Although this might be less efficient than one might wish, the 
    situation in question is not likely to occur often.

<div style="clear:both"></div>