This file contains notes regarding the implementation of the OTA extension.
User documentation is in sqlite3ota.h.

SQLite Hacks
------------


1) PRAGMA pager_ota_mode=1:

  This pragma sets a flag on the pager associated with the main database only.
  In a zipvfs system, this pragma is intercepted by zipvfs and the flag is set
  on the lower level pager only.

  The flag can only be set when there is no open transaction and the pager does
  not already have an open WAL file. Attempting to do so is an error.

  Once the flag has been set, it is not possible to open a regular WAL file.
  If, when the next read-transaction is opened, a *-wal file is found or the
  database header flags indicate that it is a wal-mode database,
  SQLITE_CANTOPEN is returned.

  Otherwise, if no WAL file or flags are found, the pager opens the *-oal file
  and uses it as a write-ahead-log with the *-shm data stored in heap-memory.

  The 8-bytes of "salt" at the start of an *-oal file is a copy of the 8 bytes
  starting at offset 24 of the database file header (the change counter and the
  number of pages in the file). If the *-oal file already exists when it is
  opened, SQLite checks that the salt still matches the database header fields.
  If not, it concludes that the database file has been written by a
  rollback-mode client since the *-oal wa created and an SQLITE_BUSY_SNAPSHOT
  error is returned. No read-transaction can be opened in this case.

  A pager with the pager_ota_mode flag set never runs a checkpoint.

  Other clients see a rollback-mode database on which the pager_ota_mode client
  is holding a SHARED lock. There are no locks to arbitrate between multiple
  pager_ota_mode connections. If two or more such connections attempt to write
  simultaneously, the results are undefined.

2) PRAGMA pager_ota_mode=2:

  The pager_ota_mode pragma may also be set to 2 if the main database is open 
  in WAL mode. This prevents SQLite from checkpointing the wal file as part
  of sqlite3_close().

  The effects of setting pager_ota_mode=2 if the db is not in WAL mode are
  undefined.

3) sqlite3_ckpt_open/step/close()

  API for performing (and resuming) incremental checkpoints.


The OTA extension
-----------------

The OTA extension requires that the OTA update be packaged as an SQLite
database. The tables it expects to find are described in sqlite3ota.h.
Essentially, for each table xyz in the target database that the user wishes
to write to, a corresponding data_xyz table is created in the OTA database
and populated with one row for each row to update, insert or delete from 
the target table.

The OTA extension opens the target and OTA update databases using a single
database handle (the target database is "main", and the OTA update database is
attached as "ota"). It executes both the "pager_ota_mode" and "ota_mode"
pragmas described above. For each data_xyz table in then:

  * CREATEs an ota_xyz table in the OTA update database.

  * Loops through the data_xyz table, running the INSERT, UPDATE or DELETE
    command on the corresponding target database table. Only the main b-tree 
    is updated by these statements. Modified pages are appended to the *-oal
    file.

    Temporary triggers installed on the target database catch the old.* 
    values associated with any UPDATEd or DELETEd rows and store them in
    the ota_xyz table (in the OTA update database).

  * For each index on the data_xyz table in the target database:

    Loop through a union of the data_xyz and ota_xyz tables in the order
    specified by the data_xyz index. In other words, if the index is on
    columns (a, b), read rows from the OTA update database using:

      SELECT * FROM data_xyz UNION ALL ota_xyz ORDER BY a, b;

    For each row visited, use an sqlite3_index_writer() VM to update the index 
    in the target database.

  * DROPs the ota_xyz table.

At any point in the above, the process may be suspended by the user. In this
case the "ota_state" table is created in the OTA database, containing a single
row indicating the current table/index being processed and the number of updates
already performed on it, and the transaction on the target database is committed
to the *-oal file. The next OTA client will use the contents of the ota_state
table to continue the update from where this one left off.

Alternatively, if the OTA update is completely applied, the transaction is
committed to the *-oal file and the database connection closed. sqlite3ota.c
then uses a rename() call to move the *-oal file to the corresponding *-wal
path. At that point it is finished - it does not take responsibility for
checkpointing the *-wal file.


Problems
--------

The rename() call might not be portable. And in theory it is unsafe if some
other client starts writing the db file.

When state is saved, the commit to the *-oal file and the commit to the OTA
update database are not atomic. So if the power fails at the wrong moment they
might get out of sync. As the main database will be committed before the OTA
update database this will likely either just pass unnoticed, or result in
SQLITE_CONSTRAINT errors (due to UNIQUE constraint violations).

If some client does modify the target database mid OTA update, or some other
error occurs, the OTA extension will keep throwing errors. It's not really
clear how to get out of this state. The system could just by delete the OTA
update database and *-oal file and have the device download the update again
and start over.

At present, for an UPDATE, both the new.* and old.* records are collected in
the ota_xyz table. And for both UPDATEs and DELETEs all fields are collected.
This means we're probably writing a lot more data to disk when saving the
state of an ongoing update to the OTA update database than is strictly
necessary.

** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************





































































*/

#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <unistd.h>

................................................................................
  return pOta->nProgress;
}

/**************************************************************************
** Beginning of OTA VFS shim methods. The VFS shim modifies the behaviour
** of a standard VFS in the following ways:
**
**   1. Whenever the first page of a main database file is read or 
**      written, the value of the change-counter cookie is stored in
**      ota_file.iCookie. Similarly, the value of the "write-version"
**      database header field is stored in ota_file.iWriteVer. This ensures
**      that the values are always trustworthy within an open transaction.
**
**   2. When the ota handle is in OTA_STAGE_OAL or OTA_STAGE_CKPT state, all
**      EXCLUSIVE lock attempts on the target database fail. This prevents
**      sqlite3_close() from running an automatic checkpoint. Until the
**      ota handle reaches OTA_STAGE_DONE - at that point the automatic
**      checkpoint may be required to delete the *-wal file.
**
**   3. In OTA_STAGE_OAL, the *-shm file is stored in memory. All xShmLock()
**      calls are noops. This is just an optimization.

**
**   4. In OTA_STAGE_OAL mode, when SQLite calls xAccess() to check if a
**      *-wal file associated with the target database exists, the following
**      special handling applies:


**
**        a) if the *-wal file does exist, return SQLITE_CANTOPEN. An OTA
**           target database may not be in wal mode already.
**
**        b) if the *-wal file does not exist, set the output parameter to
**           non-zero (to tell SQLite that it does exist) anyway.
**
**   5. In OTA_STAGE_OAL mode, if SQLite tries to open a *-wal file 
**      associated with a target database, open the corresponding *-oal file















**      instead.










*/

/*
** Close an ota file.
*/
static int otaVfsClose(sqlite3_file *pFile){
  ota_file *p = (ota_file*)pFile;

** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
**
**
** OVERVIEW 
**
**  The OTA extension requires that the OTA update be packaged as an
**  SQLite database. The tables it expects to find are described in
**  sqlite3ota.h.  Essentially, for each table xyz in the target database
**  that the user wishes to write to, a corresponding data_xyz table is
**  created in the OTA database and populated with one row for each row to
**  update, insert or delete from the target table.
** 
**  The update proceeds in three stages:
** 
**  1) The database is updated. The modified database pages are written
**     to a *-oal file. A *-oal file is just like a *-wal file, except
**     that it is named "<database>-oal" instead of "<database>-wal".
**     Because regular SQLite clients do not look for file named
**     "<database>-oal", they go on using the original database in
**     rollback mode while the *-oal file is being generated.
** 
**     During this stage OTA does not update the database by writing
**     directly to the target tables. Instead it creates "imposter"
**     tables using the SQLITE_TESTCTRL_IMPOSTER interface that it uses
**     to update each b-tree individually. All updates required by each
**     b-tree are completed before moving on to the next, and all
**     updates are done in sorted key order.
** 
**  2) The "<database>-oal" file is moved to the equivalent "<database>-wal"
**     location using a call to rename(2). Before doing this the OTA
**     module takes an EXCLUSIVE lock on the database file, ensuring
**     that there are no other active readers.
** 
**     Once the EXCLUSIVE lock is released, any other database readers
**     detect the new *-wal file and read the database in wal mode. At
**     this point they see the new version of the database - including
**     the updates made as part of the OTA update.
** 
**  3) The new *-wal file is checkpointed. This proceeds in the same way 
**     as a regular database checkpoint, except that a single frame is
**     checkpointed each time sqlite3ota_step() is called. If the OTA
**     handle is closed before the entire *-wal file is checkpointed,
**     the checkpoint progress is saved in the OTA database and the
**     checkpoint can be resumed by another OTA client at some point in
**     the future.
**
** POTENTIAL PROBLEMS
** 
**  The rename() call might not be portable. And OTA is not currently
**  syncing the directory after renaming the file.
**
**  When state is saved, any commit to the *-oal file and the commit to
**  the OTA update database are not atomic. So if the power fails at the
**  wrong moment they might get out of sync. As the main database will be
**  committed before the OTA update database this will likely either just
**  pass unnoticed, or result in SQLITE_CONSTRAINT errors (due to UNIQUE
**  constraint violations).
**
**  If some client does modify the target database mid OTA update, or some
**  other error occurs, the OTA extension will keep throwing errors. It's
**  not really clear how to get out of this state. The system could just
**  by delete the OTA update database and *-oal file and have the device
**  download the update again and start over.
**
**  At present, for an UPDATE, both the new.* and old.* records are
**  collected in the ota_xyz table. And for both UPDATEs and DELETEs all
**  fields are collected.  This means we're probably writing a lot more
**  data to disk when saving the state of an ongoing update to the OTA
**  update database than is strictly necessary.
** 
*/

#include <assert.h>
#include <string.h>
#include <stdio.h>
#include <unistd.h>

................................................................................
  return pOta->nProgress;
}

/**************************************************************************
** Beginning of OTA VFS shim methods. The VFS shim modifies the behaviour
** of a standard VFS in the following ways:
**
** 1. Whenever the first page of a main database file is read or 
**    written, the value of the change-counter cookie is stored in
**    ota_file.iCookie. Similarly, the value of the "write-version"
**    database header field is stored in ota_file.iWriteVer. This ensures
**    that the values are always trustworthy within an open transaction.
**
** 2. Whenever an SQLITE_OPEN_WAL file is opened, the (ota_file.pWalFd)
**    member variable of the associated database file descriptor is set
**    to point to the new file. A mutex protected linked list of all main 
**    db fds opened using a particular OTA VFS is maintained at 
**    ota_vfs.pMain to facilitate this.
**
** 3. Using a new file-control "SQLITE_FCNTL_OTA", a main db ota_file 
**    object can be marked as the target database of an OTA update. This
**    turns on the following extra special behaviour:
**

** 3a. If xAccess() is called to check if there exists a *-wal file 
**     associated with an OTA target database currently in OTA_STAGE_OAL
**     stage (preparing the *-oal file), the following special handling
**     applies:
**
**      * if the *-wal file does exist, return SQLITE_CANTOPEN. An OTA
**        target database may not be in wal mode already.
**
**      * if the *-wal file does not exist, set the output parameter to
**        non-zero (to tell SQLite that it does exist) anyway.
**


**     Then, when xOpen() is called to open the *-wal file associated with
**     the OTA target in OTA_STAGE_OAL stage, instead of opening the *-wal
**     file, the ota vfs opens the corresponding *-oal file instead. 
**
** 3b. The *-shm pages returned by xShmMap() for a target db file in
**     OTA_STAGE_OAL mode are actually stored in heap memory. This is to
**     avoid creating a *-shm file on disk. Additionally, xShmLock() calls
**     are no-ops on target database files in OTA_STAGE_OAL mode. This is
**     because assert() statements in some VFS implementations fail if 
**     xShmLock() is called before xShmMap().
**
** 3c. If an EXCLUSIVE lock is attempted on a target database file in any
**     mode except OTA_STAGE_DONE (all work completed and checkpointed), it 
**     fails with an SQLITE_BUSY error. This is to stop OTA connections
**     from automatically checkpointing a *-wal (or *-oal) file from within
**     sqlite3_close().
**
** 3d. In OTA_STAGE_CAPTURE mode, all xRead() calls on the wal file, and
**     all xWrite() calls on the target database file perform no IO. 
**     Instead the frame and page numbers that would be read and written
**     are recorded. Additionally, successful attempts to obtain exclusive
**     xShmLock() WRITER, CHECKPOINTER and READ0 locks on the target 
**     database file are recorded. xShmLock() calls to unlock the same
**     locks are no-ops (so that once obtained, these locks are never
**     relinquished). Finally, calls to xSync() on the target database
**     file fail with SQLITE_INTERNAL errors.
*/

/*
** Close an ota file.
*/
static int otaVfsClose(sqlite3_file *pFile){
  ota_file *p = (ota_file*)pFile;

** b-tree indexes that are collectively larger than the available cache
** memory can be very inefficient. 
**
** The problem is that in order to update a b-tree, the leaf page (at least)
** containing the entry being inserted or deleted must be modified. If the
** working set of leaves is larger than the available cache memory, then a 
** single leaf that is modified more than once as part of the transaction 
** may be loaded from or written to the persistent media more than once. 
** Additionally, because the index updates are likely to be applied in
** random order, access to pages within the databse is also likely to be in 
** random order, which is itself quite inefficient.
**
** One way to improve the situation is to sort the operations on each index
** by index key before applying them to the b-tree. This leads to an IO
** pattern that resembles a single linear scan through the index b-tree,
** and all but guarantees each modified leaf page is loaded and stored 
** exactly once. SQLite uses this trick to improve the performance of
** CREATE INDEX commands. This extension allows it to be used to improve
** the performance of large transactions on existing databases.
**
** Additionally, this extension allows the work involved in writing the 
** large transaction to be broken down into sub-transactions performed 
** sequentially by separate processes. This is useful if the system cannot 
** guarantee that a single update process may run for long enough to apply 
** the entire update, for example because the update is running on a mobile
** device that is frequently rebooted. Even after the writer process has 
** committed one or more sub-transactions, other database clients continue
** to read from the original database snapshot. In other words, partially 
** applied transactions are not visible to other clients. 
**
** "OTA" stands for "Over The Air" update. As in a large database update
** transmitted via a wireless network to a mobile device. A transaction
** applied using this extension is hence refered to as an "OTA update".
**
................................................................................
**
**   * The transaction must consist of INSERT, UPDATE and DELETE operations
**     only.
**
**   * INSERT statements may not use any default values.
**
**   * UPDATE and DELETE statements must identify their target rows by 
**     PRIMARY KEY values. If the table being written has no PRIMARY KEY
**     declaration, affected rows must be identified by rowid.
**
**   * UPDATE statements may not modify PRIMARY KEY columns.
**
**   * No triggers will be fired.
**
**   * No foreign key violations are detected or reported.
**
................................................................................
** update, the corresponding data_% table should contain a single record
** with the "ota_control" column set to contain a value of type text.
** The real primary key values identifying the row to update should be 
** stored in the corresponding columns of the data_% table row, as should
** the new values of all columns being update. The text value in the 
** "ota_control" column must contain the same number of characters as
** there are columns in the target database table, and must consist entirely
** of "x" and "." characters. For each column that is being updated,
** the corresponding character is set to "x". For those that remain as
** they are, the corresponding character of the ota_control value should
** be set to ".". For example, given the tables above, the update 
** statement:
**
**   UPDATE t1 SET c = 'usa' WHERE a = 4;
**
** is represented by the data_t1 row created by:
**
**   INSERT INTO data_t1(a, b, c, ota_control) VALUES(4, NULL, 'usa', '..x');
**
................................................................................
**     3) Calls the sqlite3ota_step() function one or more times on
**        the new handle. Each call to sqlite3ota_step() performs a single
**        b-tree operation, so thousands of calls may be required to apply 
**        a complete update.
**
**     4) Calls sqlite3ota_close() to close the OTA update handle. If
**        sqlite3ota_step() has been called enough times to completely
**        apply the update to the target database, then it is committed
**        and made visible to other database clients at this point. 
**        Otherwise, the state of the OTA update application is saved
**        in the OTA database for later resumption.

**
** See comments below for more detail on APIs.
**
** If an update is only partially applied to the target database by the
** time sqlite3ota_close() is called, various state information is saved 
** within the OTA database. This allows subsequent processes to automatically
** resume the OTA update from where it left off.
................................................................................
** that immediately return the same value.
*/
int sqlite3ota_step(sqlite3ota *pOta);

/*
** Close an OTA handle. 
**
** If the OTA update has been completely applied, commit it to the target
** database. Otherwise, assuming no error has occurred, save the current
** state of the OTA update appliation to the OTA database.
**
** If an error has already occurred as part of an sqlite3ota_step()
** or sqlite3ota_open() call, or if one occurs within this function, an
** SQLite error code is returned. Additionally, *pzErrmsg may be set to
** point to a buffer containing a utf-8 formatted English language error
** message. It is the responsibility of the caller to eventually free any 
** such buffer using sqlite3_free().

** b-tree indexes that are collectively larger than the available cache
** memory can be very inefficient. 
**
** The problem is that in order to update a b-tree, the leaf page (at least)
** containing the entry being inserted or deleted must be modified. If the
** working set of leaves is larger than the available cache memory, then a 
** single leaf that is modified more than once as part of the transaction 
** may be loaded from or written to the persistent media multiple times.
** Additionally, because the index updates are likely to be applied in
** random order, access to pages within the database is also likely to be in 
** random order, which is itself quite inefficient.
**
** One way to improve the situation is to sort the operations on each index
** by index key before applying them to the b-tree. This leads to an IO
** pattern that resembles a single linear scan through the index b-tree,
** and all but guarantees each modified leaf page is loaded and stored 
** exactly once. SQLite uses this trick to improve the performance of
** CREATE INDEX commands. This extension allows it to be used to improve
** the performance of large transactions on existing databases.
**
** Additionally, this extension allows the work involved in writing the 
** large transaction to be broken down into sub-transactions performed 
** sequentially by separate processes. This is useful if the system cannot 
** guarantee that a single update process will run for long enough to apply 
** the entire update, for example because the update is being applied on a 
** mobile device that is frequently rebooted. Even after the writer process 
** has committed one or more sub-transactions, other database clients continue
** to read from the original database snapshot. In other words, partially 
** applied transactions are not visible to other clients. 
**
** "OTA" stands for "Over The Air" update. As in a large database update
** transmitted via a wireless network to a mobile device. A transaction
** applied using this extension is hence refered to as an "OTA update".
**
................................................................................
**
**   * The transaction must consist of INSERT, UPDATE and DELETE operations
**     only.
**
**   * INSERT statements may not use any default values.
**
**   * UPDATE and DELETE statements must identify their target rows by 
**     PRIMARY KEY values. If the table being written has no PRIMARY KEY,
**     affected rows must be identified by rowid.
**
**   * UPDATE statements may not modify PRIMARY KEY columns.
**
**   * No triggers will be fired.
**
**   * No foreign key violations are detected or reported.
**
................................................................................
** update, the corresponding data_% table should contain a single record
** with the "ota_control" column set to contain a value of type text.
** The real primary key values identifying the row to update should be 
** stored in the corresponding columns of the data_% table row, as should
** the new values of all columns being update. The text value in the 
** "ota_control" column must contain the same number of characters as
** there are columns in the target database table, and must consist entirely
** of 'x' and '.' characters (or in some special cases 'd' - see below). For 
** each column that is being updated, the corresponding character is set to
** 'x'. For those that remain as they are, the corresponding character of the
** ota_control value should be set to '.'. For example, given the tables 
** above, the update statement:
**
**   UPDATE t1 SET c = 'usa' WHERE a = 4;
**
** is represented by the data_t1 row created by:
**
**   INSERT INTO data_t1(a, b, c, ota_control) VALUES(4, NULL, 'usa', '..x');
**
................................................................................
**     3) Calls the sqlite3ota_step() function one or more times on
**        the new handle. Each call to sqlite3ota_step() performs a single
**        b-tree operation, so thousands of calls may be required to apply 
**        a complete update.
**
**     4) Calls sqlite3ota_close() to close the OTA update handle. If
**        sqlite3ota_step() has been called enough times to completely
**        apply the update to the target database, then the OTA database

**        is marked as fully applied. Otherwise, the state of the OTA 
**        update application is saved in the OTA database for later 
**        resumption.
**
** See comments below for more detail on APIs.
**
** If an update is only partially applied to the target database by the
** time sqlite3ota_close() is called, various state information is saved 
** within the OTA database. This allows subsequent processes to automatically
** resume the OTA update from where it left off.
................................................................................
** that immediately return the same value.
*/
int sqlite3ota_step(sqlite3ota *pOta);

/*
** Close an OTA handle. 
**
** If the OTA update has been completely applied, mark the OTA database
** as fully applied. Otherwise, assuming no error has occurred, save the
** current state of the OTA update appliation to the OTA database.
**
** If an error has already occurred as part of an sqlite3ota_step()
** or sqlite3ota_open() call, or if one occurs within this function, an
** SQLite error code is returned. Additionally, *pzErrmsg may be set to
** point to a buffer containing a utf-8 formatted English language error
** message. It is the responsibility of the caller to eventually free any 
** such buffer using sqlite3_free().