/*

** 2004 May 22

**

** The author disclaims copyright to this source code.  In place of

** 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.

**

******************************************************************************

**

** This file contains code that is specific to Unix systems.

**

** $Id: os_unix.c,v 1.195 2008/07/30 17:28:04 drh Exp $

*/

#include "sqliteInt.h"

#if SQLITE_OS_UNIX              /* This file is used on unix only */

/*

** If SQLITE_ENABLE_LOCKING_STYLE is defined, then several different 

** locking implementations are provided:

**

**   * POSIX locking (the default),

**   * No locking,

**   * Dot-file locking,

**   * flock() locking,

**   * AFP locking (OSX only).

*/

/* #define SQLITE_ENABLE_LOCKING_STYLE 0 */

/*

** These #defines should enable >2GB file support on Posix if the

** underlying operating system supports it.  If the OS lacks

** large file support, these should be no-ops.

**

** Large file support can be disabled using the -DSQLITE_DISABLE_LFS switch

** on the compiler command line.  This is necessary if you are compiling

** on a recent machine (ex: RedHat 7.2) but you want your code to work

** on an older machine (ex: RedHat 6.0).  If you compile on RedHat 7.2

** without this option, LFS is enable.  But LFS does not exist in the kernel

** in RedHat 6.0, so the code won't work.  Hence, for maximum binary

** portability you should omit LFS.

*/

#ifndef SQLITE_DISABLE_LFS

# define _LARGE_FILE       1

# ifndef _FILE_OFFSET_BITS

#   define _FILE_OFFSET_BITS 64

# endif

# define _LARGEFILE_SOURCE 1

#endif

/*

** standard include files.

*/

#include <sys/types.h>

#include <sys/stat.h>

#include <fcntl.h>

#include <unistd.h>

#include <time.h>

#include <sys/time.h>

#include <errno.h>

#ifdef SQLITE_ENABLE_LOCKING_STYLE

#include <sys/ioctl.h>

#include <sys/param.h>

#include <sys/mount.h>

#endif /* SQLITE_ENABLE_LOCKING_STYLE */

/*

** If we are to be thread-safe, include the pthreads header and define

** the SQLITE_UNIX_THREADS macro.

*/

#if SQLITE_THREADSAFE

# include <pthread.h>

# define SQLITE_UNIX_THREADS 1

#endif

/*

** Default permissions when creating a new file

*/

#ifndef SQLITE_DEFAULT_FILE_PERMISSIONS

# define SQLITE_DEFAULT_FILE_PERMISSIONS 0644

#endif

/*

** Maximum supported path-length.

*/

#define MAX_PATHNAME 512

/*

** The unixFile structure is subclass of sqlite3_file specific for the unix

** protability layer.

*/

typedef struct unixFile unixFile;

struct unixFile {

  sqlite3_io_methods const *pMethod;  /* Always the first entry */

#ifdef SQLITE_TEST

  /* In test mode, increase the size of this structure a bit so that 

  ** it is larger than the struct CrashFile defined in test6.c.

  */

  char aPadding[32];

#endif

  struct openCnt *pOpen;    /* Info about all open fd's on this inode */

  struct lockInfo *pLock;   /* Info about locks on this inode */

#ifdef SQLITE_ENABLE_LOCKING_STYLE

  void *lockingContext;     /* Locking style specific state */

#endif

  int h;                    /* The file descriptor */

  unsigned char locktype;   /* The type of lock held on this fd */

  int dirfd;                /* File descriptor for the directory */

#if SQLITE_THREADSAFE

  pthread_t tid;            /* The thread that "owns" this unixFile */

#endif

};

/*

** Include code that is common to all os_*.c files

*/

#include "os_common.h"

/*

** Define various macros that are missing from some systems.

*/

#ifndef O_LARGEFILE

# define O_LARGEFILE 0

#endif

#ifdef SQLITE_DISABLE_LFS

# undef O_LARGEFILE

# define O_LARGEFILE 0

#endif

#ifndef O_NOFOLLOW

# define O_NOFOLLOW 0

#endif

#ifndef O_BINARY

# define O_BINARY 0

#endif

/*

** The DJGPP compiler environment looks mostly like Unix, but it

** lacks the fcntl() system call.  So redefine fcntl() to be something

** that always succeeds.  This means that locking does not occur under

** DJGPP.  But it is DOS - what did you expect?

*/

#ifdef __DJGPP__

# define fcntl(A,B,C) 0

#endif

/*

** The threadid macro resolves to the thread-id or to 0.  Used for

** testing and debugging only.

*/

#if SQLITE_THREADSAFE

#define threadid pthread_self()

#else

#define threadid 0

#endif

/*

** Set or check the unixFile.tid field.  This field is set when an unixFile

** is first opened.  All subsequent uses of the unixFile verify that the

** same thread is operating on the unixFile.  Some operating systems do

** not allow locks to be overridden by other threads and that restriction

** means that sqlite3* database handles cannot be moved from one thread

** to another.  This logic makes sure a user does not try to do that

** by mistake.

**

** Version 3.3.1 (2006-01-15):  unixFile can be moved from one thread to

** another as long as we are running on a system that supports threads

** overriding each others locks (which now the most common behavior)

** or if no locks are held.  But the unixFile.pLock field needs to be

** recomputed because its key includes the thread-id.  See the 

** transferOwnership() function below for additional information

*/

#if SQLITE_THREADSAFE

# define SET_THREADID(X)   (X)->tid = pthread_self()

# define CHECK_THREADID(X) (threadsOverrideEachOthersLocks==0 && \

                            !pthread_equal((X)->tid, pthread_self()))

#else

# define SET_THREADID(X)

# define CHECK_THREADID(X) 0

#endif

/*

** Here is the dirt on POSIX advisory locks:  ANSI STD 1003.1 (1996)

** section 6.5.2.2 lines 483 through 490 specify that when a process

** sets or clears a lock, that operation overrides any prior locks set

** by the same process.  It does not explicitly say so, but this implies

** that it overrides locks set by the same process using a different

** file descriptor.  Consider this test case:

**       int fd2 = open("./file2", O_RDWR|O_CREAT, 0644);

**

** Suppose ./file1 and ./file2 are really the same file (because

** one is a hard or symbolic link to the other) then if you set

** an exclusive lock on fd1, then try to get an exclusive lock

** on fd2, it works.  I would have expected the second lock to

** fail since there was already a lock on the file due to fd1.

** But not so.  Since both locks came from the same process, the

** second overrides the first, even though they were on different

** file descriptors opened on different file names.

**

** Bummer.  If you ask me, this is broken.  Badly broken.  It means

** that we cannot use POSIX locks to synchronize file access among

** competing threads of the same process.  POSIX locks will work fine

** to synchronize access for threads in separate processes, but not

** threads within the same process.

**

** To work around the problem, SQLite has to manage file locks internally

** on its own.  Whenever a new database is opened, we have to find the

** specific inode of the database file (the inode is determined by the

** st_dev and st_ino fields of the stat structure that fstat() fills in)

** and check for locks already existing on that inode.  When locks are

** created or removed, we have to look at our own internal record of the

** locks to see if another thread has previously set a lock on that same

** inode.

**

** The sqlite3_file structure for POSIX is no longer just an integer file

** descriptor.  It is now a structure that holds the integer file

** descriptor and a pointer to a structure that describes the internal

** locks on the corresponding inode.  There is one locking structure

** per inode, so if the same inode is opened twice, both unixFile structures

** point to the same locking structure.  The locking structure keeps

** a reference count (so we will know when to delete it) and a "cnt"

** field that tells us its internal lock status.  cnt==0 means the

** file is unlocked.  cnt==-1 means the file has an exclusive lock.

** cnt>0 means there are cnt shared locks on the file.

**

** Any attempt to lock or unlock a file first checks the locking

** structure.  The fcntl() system call is only invoked to set a 

** POSIX lock if the internal lock structure transitions between

** a locked and an unlocked state.

**

** 2004-Jan-11:

** More recent discoveries about POSIX advisory locks.  (The more

** I discover, the more I realize the a POSIX advisory locks are

** an abomination.)

**

** If you close a file descriptor that points to a file that has locks,

** all locks on that file that are owned by the current process are

** released.  To work around this problem, each unixFile structure contains

** a pointer to an openCnt structure.  There is one openCnt structure

** per open inode, which means that multiple unixFile can point to a single

** openCnt.  When an attempt is made to close an unixFile, if there are

** other unixFile open on the same inode that are holding locks, the call

** to close() the file descriptor is deferred until all of the locks clear.

** The openCnt structure keeps a list of file descriptors that need to

** be closed and that list is walked (and cleared) when the last lock

** clears.

**

** First, under Linux threads, because each thread has a separate

** process ID, lock operations in one thread do not override locks

** to the same file in other threads.  Linux threads behave like

** separate processes in this respect.  But, if you close a file

** descriptor in linux threads, all locks are cleared, even locks

** on other threads and even though the other threads have different

** process IDs.  Linux threads is inconsistent in this respect.

** (I'm beginning to think that linux threads is an abomination too.)

** The consequence of this all is that the hash table for the lockInfo

** structure has to include the process id as part of its key because

** locks in different threads are treated as distinct.  But the 

** openCnt structure should not include the process id in its

** key because close() clears lock on all threads, not just the current

** thread.  Were it not for this goofiness in linux threads, we could

** combine the lockInfo and openCnt structures into a single structure.

**

** 2004-Jun-28:

** On some versions of linux, threads can override each others locks.

** On others not.  Sometimes you can change the behavior on the same

** system by setting the LD_ASSUME_KERNEL environment variable.  The

** POSIX standard is silent as to which behavior is correct, as far

** as I can tell, so other versions of unix might show the same

** inconsistency.  There is no little doubt in my mind that posix

** advisory locks and linux threads are profoundly broken.

**

** To work around the inconsistencies, we have to test at runtime 

** whether or not threads can override each others locks.  This test

** is run once, the first time any lock is attempted.  A static 

** variable is set to record the results of this test for future

** use.

*/

/*

** An instance of the following structure serves as the key used

** to locate a particular lockInfo structure given its inode.

**

** If threads cannot override each others locks, then we set the

** lockKey.tid field to the thread ID.  If threads can override

** each others locks then tid is always set to zero.  tid is omitted

** if we compile without threading support.

*/

struct lockKey {

  dev_t dev;       /* Device number */

  ino_t ino;       /* Inode number */

#if SQLITE_THREADSAFE

  pthread_t tid;   /* Thread ID or zero if threads can override each other */

#endif

};

/*

** An instance of the following structure is allocated for each open

** inode on each thread with a different process ID.  (Threads have

** different process IDs on linux, but not on most other unixes.)

**

** A single inode can have multiple file descriptors, so each unixFile

** structure contains a pointer to an instance of this object and this

** object keeps a count of the number of unixFile pointing to it.

*/

struct lockInfo {

  struct lockKey key;  /* The lookup key */

  int cnt;             /* Number of SHARED locks held */

  int locktype;        /* One of SHARED_LOCK, RESERVED_LOCK etc. */

  int nRef;            /* Number of pointers to this structure */

  struct lockInfo *pNext, *pPrev;   /* List of all lockInfo objects */

};

/*

** An instance of the following structure serves as the key used

** to locate a particular openCnt structure given its inode.  This

** is the same as the lockKey except that the thread ID is omitted.

*/

struct openKey {

  dev_t dev;   /* Device number */

  ino_t ino;   /* Inode number */

};

/*

** An instance of the following structure is allocated for each open

** inode.  This structure keeps track of the number of locks on that

** inode.  If a close is attempted against an inode that is holding

** locks, the close is deferred until all locks clear by adding the

** file descriptor to be closed to the pending list.

*/

struct openCnt {

  struct openKey key;   /* The lookup key */

  int nRef;             /* Number of pointers to this structure */

  int nLock;            /* Number of outstanding locks */

  int nPending;         /* Number of pending close() operations */

  int *aPending;        /* Malloced space holding fd's awaiting a close() */

  struct openCnt *pNext, *pPrev;   /* List of all openCnt objects */

};

/*

** List of all lockInfo and openCnt objects.  This used to be a hash

** table.  But the number of objects is rarely more than a dozen and

** never exceeds a few thousand.  And lookup is not on a critical

** path oo a simple linked list will suffice.

*/

static struct lockInfo *lockList = 0;

static struct openCnt *openList = 0;

/*

** The locking styles are associated with the different file locking

** capabilities supported by different file systems.  

**

** POSIX locking style fully supports shared and exclusive byte-range locks 

** AFP locking only supports exclusive byte-range locks

** FLOCK only supports a single file-global exclusive lock

** DOTLOCK isn't a true locking style, it refers to the use of a special

**   file named the same as the database file with a '.lock' extension, this

**   can be used on file systems that do not offer any reliable file locking

** NO locking means that no locking will be attempted, this is only used for

**   read-only file systems currently

** UNSUPPORTED means that no locking will be attempted, this is only used for

**   file systems that are known to be unsupported

*/

#define LOCKING_STYLE_POSIX        1

#define LOCKING_STYLE_NONE         2

#define LOCKING_STYLE_DOTFILE      3

#define LOCKING_STYLE_FLOCK        4

#define LOCKING_STYLE_AFP          5

/*

** Helper functions to obtain and relinquish the global mutex.

*/

static void enterMutex(){

  sqlite3_mutex_enter(sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MASTER));

}

static void leaveMutex(){

  sqlite3_mutex_leave(sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MASTER));

}

#if SQLITE_THREADSAFE

/*

** This variable records whether or not threads can override each others

** locks.

**

**    0:  No.  Threads cannot override each others locks.

**    1:  Yes.  Threads can override each others locks.

**   -1:  We don't know yet.

**

** On some systems, we know at compile-time if threads can override each

** others locks.  On those systems, the SQLITE_THREAD_OVERRIDE_LOCK macro

** will be set appropriately.  On other systems, we have to check at

** runtime.  On these latter systems, SQLTIE_THREAD_OVERRIDE_LOCK is

** undefined.

**

** This variable normally has file scope only.  But during testing, we make

** it a global so that the test code can change its value in order to verify

** that the right stuff happens in either case.

*/

#ifndef SQLITE_THREAD_OVERRIDE_LOCK

# define SQLITE_THREAD_OVERRIDE_LOCK -1

#endif

#ifdef SQLITE_TEST

int threadsOverrideEachOthersLocks = SQLITE_THREAD_OVERRIDE_LOCK;

#else

static int threadsOverrideEachOthersLocks = SQLITE_THREAD_OVERRIDE_LOCK;

#endif

/*

** This structure holds information passed into individual test

** threads by the testThreadLockingBehavior() routine.

*/

struct threadTestData {

  int fd;                /* File to be locked */

  struct flock lock;     /* The locking operation */

  int result;            /* Result of the locking operation */

};

#ifdef SQLITE_LOCK_TRACE

/*

** Print out information about all locking operations.

**

** This routine is used for troubleshooting locks on multithreaded

** platforms.  Enable by compiling with the -DSQLITE_LOCK_TRACE

** command-line option on the compiler.  This code is normally

** turned off.

*/

static int lockTrace(int fd, int op, struct flock *p){

  char *zOpName, *zType;

  int s;

  int savedErrno;

  if( op==F_GETLK ){

    zOpName = "GETLK";

  }else if( op==F_SETLK ){

    zOpName = "SETLK";

  }else{

    s = fcntl(fd, op, p);

    sqlite3DebugPrintf("fcntl unknown %d %d %d\n", fd, op, s);

    return s;

  }

  if( p->l_type==F_RDLCK ){

    zType = "RDLCK";

  }else if( p->l_type==F_WRLCK ){

    zType = "WRLCK";

  }else if( p->l_type==F_UNLCK ){

    zType = "UNLCK";

  }else{

    assert( 0 );

  }

  assert( p->l_whence==SEEK_SET );

  s = fcntl(fd, op, p);

  savedErrno = errno;

  sqlite3DebugPrintf("fcntl %d %d %s %s %d %d %d %d\n",

     threadid, fd, zOpName, zType, (int)p->l_start, (int)p->l_len,

     (int)p->l_pid, s);

  if( s==(-1) && op==F_SETLK && (p->l_type==F_RDLCK || p->l_type==F_WRLCK) ){

    struct flock l2;

    l2 = *p;

    fcntl(fd, F_GETLK, &l2);

    if( l2.l_type==F_RDLCK ){

      zType = "RDLCK";

    }else if( l2.l_type==F_WRLCK ){

      zType = "WRLCK";

    }else if( l2.l_type==F_UNLCK ){

      zType = "UNLCK";

    }else{

      assert( 0 );

    }

    sqlite3DebugPrintf("fcntl-failure-reason: %s %d %d %d\n",

       zType, (int)l2.l_start, (int)l2.l_len, (int)l2.l_pid);

  }

  errno = savedErrno;

  return s;

}

#define fcntl lockTrace

#endif /* SQLITE_LOCK_TRACE */

/*

** The testThreadLockingBehavior() routine launches two separate

** threads on this routine.  This routine attempts to lock a file

** descriptor then returns.  The success or failure of that attempt

** allows the testThreadLockingBehavior() procedure to determine

** whether or not threads can override each others locks.

*/

static void *threadLockingTest(void *pArg){

  struct threadTestData *pData = (struct threadTestData*)pArg;

  pData->result = fcntl(pData->fd, F_SETLK, &pData->lock);

  return pArg;

}

/*

** This procedure attempts to determine whether or not threads

** can override each others locks then sets the 

** threadsOverrideEachOthersLocks variable appropriately.

*/

static void testThreadLockingBehavior(int fd_orig){

  int fd;

  struct threadTestData d[2];

  pthread_t t[2];

  fd = dup(fd_orig);

  if( fd<0 ) return;

  memset(d, 0, sizeof(d));

  d[0].fd = fd;

  d[0].lock.l_type = F_RDLCK;

  d[0].lock.l_len = 1;

  d[0].lock.l_start = 0;

  d[0].lock.l_whence = SEEK_SET;

  d[1] = d[0];

  d[1].lock.l_type = F_WRLCK;

  pthread_create(&t[0], 0, threadLockingTest, &d[0]);

  pthread_create(&t[1], 0, threadLockingTest, &d[1]);

  pthread_join(t[0], 0);

  pthread_join(t[1], 0);

  close(fd);

  threadsOverrideEachOthersLocks =  d[0].result==0 && d[1].result==0;

}

#endif /* SQLITE_THREADSAFE */

/*

** Release a lockInfo structure previously allocated by findLockInfo().

*/

static void releaseLockInfo(struct lockInfo *pLock){

  if( pLock ){

    pLock->nRef--;

    if( pLock->nRef==0 ){

      if( pLock->pPrev ){

        assert( pLock->pPrev->pNext==pLock );

        pLock->pPrev->pNext = pLock->pNext;

      }else{

        assert( lockList==pLock );

        lockList = pLock->pNext;

      }

      if( pLock->pNext ){

        assert( pLock->pNext->pPrev==pLock );

        pLock->pNext->pPrev = pLock->pPrev;

      }

      sqlite3_free(pLock);

    }

  }

}

/*

** Release a openCnt structure previously allocated by findLockInfo().

*/

static void releaseOpenCnt(struct openCnt *pOpen){

  if( pOpen ){

    pOpen->nRef--;

    if( pOpen->nRef==0 ){

      if( pOpen->pPrev ){

        assert( pOpen->pPrev->pNext==pOpen );

        pOpen->pPrev->pNext = pOpen->pNext;

      }else{

        assert( openList==pOpen );

        openList = pOpen->pNext;

      }

      if( pOpen->pNext ){

        assert( pOpen->pNext->pPrev==pOpen );

        pOpen->pNext->pPrev = pOpen->pPrev;

      }

      sqlite3_free(pOpen->aPending);

      sqlite3_free(pOpen);

    }

  }

}

#ifdef SQLITE_ENABLE_LOCKING_STYLE

/*

** Tests a byte-range locking query to see if byte range locks are 

** supported, if not we fall back to dotlockLockingStyle.

*/

static int testLockingStyle(int fd){

  struct flock lockInfo;

  /* Test byte-range lock using fcntl(). If the call succeeds, 

  ** assume that the file-system supports POSIX style locks. 

  */

  lockInfo.l_len = 1;

  lockInfo.l_start = 0;

  lockInfo.l_whence = SEEK_SET;

  lockInfo.l_type = F_RDLCK;

  if( fcntl(fd, F_GETLK, &lockInfo)!=-1 ) {

    return LOCKING_STYLE_POSIX;

  }

  /* Testing for flock() can give false positives.  So if if the above 

  ** test fails, then we fall back to using dot-file style locking.

  */  

  return LOCKING_STYLE_DOTFILE;

}

#endif

/* 

** If SQLITE_ENABLE_LOCKING_STYLE is defined, this function Examines the 

** f_fstypename entry in the statfs structure as returned by stat() for 

** the file system hosting the database file and selects  the appropriate

** locking style based on its value.  These values and assignments are 

** based on Darwin/OSX behavior and have not been thoroughly tested on 

** other systems.

**

** If SQLITE_ENABLE_LOCKING_STYLE is not defined, this function always

** returns LOCKING_STYLE_POSIX.

*/

static int detectLockingStyle(

  sqlite3_vfs *pVfs,

  const char *filePath, 

  int fd

){

#ifdef SQLITE_ENABLE_LOCKING_STYLE

  struct Mapping {

    const char *zFilesystem;

    int eLockingStyle;

  } aMap[] = {

    { "hfs",    LOCKING_STYLE_POSIX },

    { "ufs",    LOCKING_STYLE_POSIX },

    { "afpfs",  LOCKING_STYLE_AFP },

    { "smbfs",  LOCKING_STYLE_FLOCK },

    { "msdos",  LOCKING_STYLE_DOTFILE },

    { "webdav", LOCKING_STYLE_NONE },

    { 0, 0 }

  };

  int i;

  struct statfs fsInfo;

  if( !filePath ){

    return LOCKING_STYLE_NONE;

  }

  if( pVfs->pAppData ){

    return (int)pVfs->pAppData;

  }

  if( statfs(filePath, &fsInfo) != -1 ){

    if( fsInfo.f_flags & MNT_RDONLY ){

      return LOCKING_STYLE_NONE;

    }

    for(i=0; aMap[i].zFilesystem; i++){

      if( strcmp(fsInfo.f_fstypename, aMap[i].zFilesystem)==0 ){

        return aMap[i].eLockingStyle;

      }

    }

  }

  /* Default case. Handles, amongst others, "nfs". */

  return testLockingStyle(fd);  

#endif

  return LOCKING_STYLE_POSIX;

}

/*

** Given a file descriptor, locate lockInfo and openCnt structures that

** describes that file descriptor.  Create new ones if necessary.  The

** return values might be uninitialized if an error occurs.

**

** Return an appropriate error code.

*/

static int findLockInfo(

  int fd,                      /* The file descriptor used in the key */

  struct lockInfo **ppLock,    /* Return the lockInfo structure here */

  struct openCnt **ppOpen      /* Return the openCnt structure here */

){

  int rc;

  struct lockKey key1;

  struct openKey key2;

  struct stat statbuf;

  struct lockInfo *pLock;

  struct openCnt *pOpen;

  rc = fstat(fd, &statbuf);

  if( rc!=0 ){

#ifdef EOVERFLOW

    if( errno==EOVERFLOW ) return SQLITE_NOLFS;

#endif

    return SQLITE_IOERR;

  }

  /* On OS X on an msdos filesystem, the inode number is reported

  ** incorrectly for zero-size files.  See ticket #3260.  To work

  ** around this problem (we consider it a bug in OS X, not SQLite)

  ** we always increase the file size to 1 by writing a single byte

  ** prior to accessing the inode number.  The one byte written is

  ** an ASCII 'S' character which also happens to be the first byte

  ** in the header of every SQLite database.  In this way, if there

  ** is a race condition such that another thread has already populated

  ** the first page of the database, no damage is done.

  */

  if( statbuf.st_size==0 ){

    write(fd, "S", 1);

    rc = fstat(fd, &statbuf);

    if( rc!=0 ){

      return SQLITE_IOERR;

    }

  }

  memset(&key1, 0, sizeof(key1));

  key1.dev = statbuf.st_dev;

  key1.ino = statbuf.st_ino;

#if SQLITE_THREADSAFE

  if( threadsOverrideEachOthersLocks<0 ){

    testThreadLockingBehavior(fd);

  }

  key1.tid = threadsOverrideEachOthersLocks ? 0 : pthread_self();

#endif

  memset(&key2, 0, sizeof(key2));

  key2.dev = statbuf.st_dev;

  key2.ino = statbuf.st_ino;

  pLock = lockList;

  while( pLock && memcmp(&key1, &pLock->key, sizeof(key1)) ){

    pLock = pLock->pNext;

  }

  if( pLock==0 ){

    pLock = sqlite3_malloc( sizeof(*pLock) );

    if( pLock==0 ){

      rc = SQLITE_NOMEM;

      goto exit_findlockinfo;

    }

    pLock->key = key1;

    pLock->nRef = 1;

    pLock->cnt = 0;

    pLock->locktype = 0;

    pLock->pNext = lockList;

    pLock->pPrev = 0;

    if( lockList ) lockList->pPrev = pLock;

    lockList = pLock;

  }else{

    pLock->nRef++;

  }

  *ppLock = pLock;

  if( ppOpen!=0 ){

    pOpen = openList;

    while( pOpen && memcmp(&key2, &pOpen->key, sizeof(key2)) ){

      pOpen = pOpen->pNext;

    }

    if( pOpen==0 ){

      pOpen = sqlite3_malloc( sizeof(*pOpen) );

      if( pOpen==0 ){

        releaseLockInfo(pLock);

        rc = SQLITE_NOMEM;

        goto exit_findlockinfo;

      }

      pOpen->key = key2;

      pOpen->nRef = 1;

      pOpen->nLock = 0;

      pOpen->nPending = 0;

      pOpen->aPending = 0;

      pOpen->pNext = openList;

      pOpen->pPrev = 0;

      if( openList ) openList->pPrev = pOpen;

      openList = pOpen;

    }else{

      pOpen->nRef++;

    }

    *ppOpen = pOpen;

  }

exit_findlockinfo:

  return rc;

}

#ifdef SQLITE_DEBUG

/*

** Helper function for printing out trace information from debugging

** binaries. This returns the string represetation of the supplied

** integer lock-type.

*/

static const char *locktypeName(int locktype){

  switch( locktype ){

  case NO_LOCK: return "NONE";

  case SHARED_LOCK: return "SHARED";

  case RESERVED_LOCK: return "RESERVED";

  case PENDING_LOCK: return "PENDING";

  case EXCLUSIVE_LOCK: return "EXCLUSIVE";

  }

  return "ERROR";

}

#endif

/*

** If we are currently in a different thread than the thread that the

** unixFile argument belongs to, then transfer ownership of the unixFile

** over to the current thread.

**

** A unixFile is only owned by a thread on systems where one thread is

** unable to override locks created by a different thread.  RedHat9 is

** an example of such a system.

**

** Ownership transfer is only allowed if the unixFile is currently unlocked.

** If the unixFile is locked and an ownership is wrong, then return

** SQLITE_MISUSE.  SQLITE_OK is returned if everything works.

*/

#if SQLITE_THREADSAFE

static int transferOwnership(unixFile *pFile){

  int rc;

  pthread_t hSelf;

  if( threadsOverrideEachOthersLocks ){

    /* Ownership transfers not needed on this system */

    return SQLITE_OK;

  }

  hSelf = pthread_self();

  if( pthread_equal(pFile->tid, hSelf) ){

    /* We are still in the same thread */

    OSTRACE1("No-transfer, same thread\n");

    return SQLITE_OK;

  }

  if( pFile->locktype!=NO_LOCK ){

    /* We cannot change ownership while we are holding a lock! */

    return SQLITE_MISUSE;

  }

  OSTRACE4("Transfer ownership of %d from %d to %d\n",

            pFile->h, pFile->tid, hSelf);

  pFile->tid = hSelf;

  if (pFile->pLock != NULL) {

    releaseLockInfo(pFile->pLock);

    rc = findLockInfo(pFile->h, &pFile->pLock, 0);

    OSTRACE5("LOCK    %d is now %s(%s,%d)\n", pFile->h,

           locktypeName(pFile->locktype),

           locktypeName(pFile->pLock->locktype), pFile->pLock->cnt);

    return rc;

  } else {

    return SQLITE_OK;

  }

}

#else

  /* On single-threaded builds, ownership transfer is a no-op */

# define transferOwnership(X) SQLITE_OK

#endif

/*

** Seek to the offset passed as the second argument, then read cnt 

** bytes into pBuf. Return the number of bytes actually read.

**

** NB:  If you define USE_PREAD or USE_PREAD64, then it might also

** be necessary to define _XOPEN_SOURCE to be 500.  This varies from

** one system to another.  Since SQLite does not define USE_PREAD

** any any form by default, we will not attempt to define _XOPEN_SOURCE.

** See tickets #2741 and #2681.

*/

static int seekAndRead(unixFile *id, sqlite3_int64 offset, void *pBuf, int cnt){

  int got;

  i64 newOffset;

  TIMER_START;

#if defined(USE_PREAD)

  got = pread(id->h, pBuf, cnt, offset);

  SimulateIOError( got = -1 );

#elif defined(USE_PREAD64)

  got = pread64(id->h, pBuf, cnt, offset);

  SimulateIOError( got = -1 );

#else

  newOffset = lseek(id->h, offset, SEEK_SET);

  SimulateIOError( newOffset-- );

  if( newOffset!=offset ){

    return -1;

  }

  got = read(id->h, pBuf, cnt);

#endif

  TIMER_END;

  OSTRACE5("READ    %-3d %5d %7lld %llu\n", id->h, got, offset, TIMER_ELAPSED);

  return got;

}

/*

** Read data from a file into a buffer.  Return SQLITE_OK if all

** bytes were read successfully and SQLITE_IOERR if anything goes

** wrong.

*/

static int unixRead(

  sqlite3_file *id, 

  void *pBuf, 

  int amt,

  sqlite3_int64 offset

){

  int got;

  assert( id );

  got = seekAndRead((unixFile*)id, offset, pBuf, amt);

  if( got==amt ){

    return SQLITE_OK;

  }else if( got<0 ){

    return SQLITE_IOERR_READ;

  }else{

    memset(&((char*)pBuf)[got], 0, amt-got);

    return SQLITE_IOERR_SHORT_READ;

  }

}

/*

** Seek to the offset in id->offset then read cnt bytes into pBuf.

** Return the number of bytes actually read.  Update the offset.

*/

static int seekAndWrite(unixFile *id, i64 offset, const void *pBuf, int cnt){

  int got;

  i64 newOffset;

  TIMER_START;

#if defined(USE_PREAD)

  got = pwrite(id->h, pBuf, cnt, offset);

#elif defined(USE_PREAD64)

  got = pwrite64(id->h, pBuf, cnt, offset);

#else

  newOffset = lseek(id->h, offset, SEEK_SET);

  if( newOffset!=offset ){

    return -1;

  }

  got = write(id->h, pBuf, cnt);

#endif

  TIMER_END;

  OSTRACE5("WRITE   %-3d %5d %7lld %llu\n", id->h, got, offset, TIMER_ELAPSED);

  return got;

}

/*

** Write data from a buffer into a file.  Return SQLITE_OK on success

** or some other error code on failure.

*/

static int unixWrite(

  sqlite3_file *id, 

  const void *pBuf, 

  int amt,

  sqlite3_int64 offset 

){

  int wrote = 0;

  assert( id );

  assert( amt>0 );

  while( amt>0 && (wrote = seekAndWrite((unixFile*)id, offset, pBuf, amt))>0 ){

    amt -= wrote;

    offset += wrote;

    pBuf = &((char*)pBuf)[wrote];

  }

  SimulateIOError(( wrote=(-1), amt=1 ));

  SimulateDiskfullError(( wrote=0, amt=1 ));

  if( amt>0 ){

    if( wrote<0 ){

      return SQLITE_IOERR_WRITE;

    }else{

      return SQLITE_FULL;

    }

  }

  return SQLITE_OK;

}

#ifdef SQLITE_TEST

/*

** Count the number of fullsyncs and normal syncs.  This is used to test

** that syncs and fullsyncs are occuring at the right times.

*/

int sqlite3_sync_count = 0;

int sqlite3_fullsync_count = 0;

#endif

/*

** Use the fdatasync() API only if the HAVE_FDATASYNC macro is defined.

** Otherwise use fsync() in its place.

*/

#ifndef HAVE_FDATASYNC

# define fdatasync fsync

#endif

/*

** Define HAVE_FULLFSYNC to 0 or 1 depending on whether or not

** the F_FULLFSYNC macro is defined.  F_FULLFSYNC is currently

** only available on Mac OS X.  But that could change.

*/

#ifdef F_FULLFSYNC

# define HAVE_FULLFSYNC 1

#else

# define HAVE_FULLFSYNC 0

#endif

/*

** The fsync() system call does not work as advertised on many

** unix systems.  The following procedure is an attempt to make

** it work better.

**

** The SQLITE_NO_SYNC macro disables all fsync()s.  This is useful

** for testing when we want to run through the test suite quickly.

** You are strongly advised *not* to deploy with SQLITE_NO_SYNC

** enabled, however, since with SQLITE_NO_SYNC enabled, an OS crash

** or power failure will likely corrupt the database file.

*/

static int full_fsync(int fd, int fullSync, int dataOnly){

  int rc;

  /* Record the number of times that we do a normal fsync() and 

  ** FULLSYNC.  This is used during testing to verify that this procedure

  ** gets called with the correct arguments.

  */

#ifdef SQLITE_TEST

  if( fullSync ) sqlite3_fullsync_count++;

  sqlite3_sync_count++;

#endif

  /* If we compiled with the SQLITE_NO_SYNC flag, then syncing is a

  ** no-op

  */