How lock is implemented upon write?

classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|

How lock is implemented upon write?

Peng Yu
Hi,

I am trying to understand how lock is implemented in sqlite3. But the
following manual page is too much such that I can figure out the main low
level implementation techniques.

https://www.sqlite.org/draft/lockingv3.html

Could anybody provide some equivalent python code (other high level
language to make the example easy to understand) on how a db file is locked
upon write? Thanks.

--
Regards,
Peng
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How lock is implemented upon write?

Simon Slavin-3
You might want to take a look at the standard VFSen:

<https://www.sqlite.org/draft/vfs.html#standard_unix_vfses>

At a low level, SQLite depends on the VFS for reliable locking.  The main parts of SQLite call a routine supplied by the VFS.  The VFS does the actual locking.

If we didn't answer your question, feel free to post again telling us what you're looking for.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How lock is implemented upon write?

Peng Yu
I not sure how to use os_unix.c. Are there any easy to follow examples in
python?

On Mon, Jul 1, 2019 at 9:08 PM Simon Slavin <[hidden email]> wrote:

> You might want to take a look at the standard VFSen:
>
> <https://www.sqlite.org/draft/vfs.html#standard_unix_vfses>
>
> At a low level, SQLite depends on the VFS for reliable locking.  The main
> parts of SQLite call a routine supplied by the VFS.  The VFS does the
> actual locking.
>
> If we didn't answer your question, feel free to post again telling us what
> you're looking for.
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
--
Regards,
Peng
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How lock is implemented upon write?

David Raymond
I don't have good answers for you as I'm not familiar with locking, but I'd suggest reading the comments in SQLite's os.h file (starting around line 91 at the moment) which I found interesting.

For Python it looks like it'd be something involving the fcntl module for Unix or the msvcrt module for Windows.


-----Original Message-----
From: sqlite-users <[hidden email]> On Behalf Of Peng Yu
Sent: Tuesday, July 02, 2019 3:26 PM
To: SQLite mailing list <[hidden email]>
Subject: Re: [sqlite] How lock is implemented upon write?

I not sure how to use os_unix.c. Are there any easy to follow examples in
python?

On Mon, Jul 1, 2019 at 9:08 PM Simon Slavin <[hidden email]> wrote:

> You might want to take a look at the standard VFSen:
>
> <https://www.sqlite.org/draft/vfs.html#standard_unix_vfses>
>
> At a low level, SQLite depends on the VFS for reliable locking.  The main
> parts of SQLite call a routine supplied by the VFS.  The VFS does the
> actual locking.
>
> If we didn't answer your question, feel free to post again telling us what
> you're looking for.
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
--
Regards,
Peng
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How lock is implemented upon write?

Keith Medcalf
In reply to this post by Peng Yu

On Tuesday, 2 July, 2019 13:26, Peng Yu <[hidden email]>:

>I not sure how to use os_unix.c. Are there any easy to follow
>examples in python?

YOU do not use os_unix.c.  Perhaps you can state what it is that you are trying to accomplish.  

For example:

I would like to know how I drive a car to the supermarket.  (Explaining how electric windows function or are designed is neither helpful nor conducive to a correct answer).

I would like to know how to write a virus that co-operates with SQLite3 advisory locking on Unix type systems in order to enable the virus to make changes to SQLite3 databases without anyones knowledge and in compliance with the current system of advisory locks, such that my changes cannot be detected by creating anomolous behaviour in applications which actually use the SQLite3 library, and will not be accidentally overwritten by one of those non-malicious applications.  Since I want to keep the size of my virus under 8K I cannot actually use the SQLite3 database engine in my malicious software.

etc.

--
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.




_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How lock is implemented upon write?

Peng Yu
As I said in my original message "I am trying to understand how lock
is implemented in sqlite3".

On 7/2/19, Keith Medcalf <[hidden email]> wrote:

>
> On Tuesday, 2 July, 2019 13:26, Peng Yu <[hidden email]>:
>
>>I not sure how to use os_unix.c. Are there any easy to follow
>>examples in python?
>
> YOU do not use os_unix.c.  Perhaps you can state what it is that you are
> trying to accomplish.
>
> For example:
>
> I would like to know how I drive a car to the supermarket.  (Explaining how
> electric windows function or are designed is neither helpful nor conducive
> to a correct answer).
>
> I would like to know how to write a virus that co-operates with SQLite3
> advisory locking on Unix type systems in order to enable the virus to make
> changes to SQLite3 databases without anyones knowledge and in compliance
> with the current system of advisory locks, such that my changes cannot be
> detected by creating anomolous behaviour in applications which actually use
> the SQLite3 library, and will not be accidentally overwritten by one of
> those non-malicious applications.  Since I want to keep the size of my virus
> under 8K I cannot actually use the SQLite3 database engine in my malicious
> software.
>
> etc.
>
> --
> The fact that there's a Highway to Hell but only a Stairway to Heaven says a
> lot about anticipated traffic volume.
>
>
>
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>


--
Regards,
Peng
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How lock is implemented upon write?

Jens Alfke-2


> On Jul 3, 2019, at 10:59 AM, Peng Yu <[hidden email]> wrote:
>
> As I said in my original message "I am trying to understand how lock
> is implemented in sqlite3".

No offense, but I don’t think it’s reasonable to ask people to port code to Python just so you can figure out how it's implemented.

If you’re seriously interested in the implementation of SQLite, you’re going to have to learn C.

Or if you just want to know how locking behaves, from a database user perspective, you could ask specific questions (that aren’t already answered in the documentation.)

—Jens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How lock is implemented upon write?

Keith Medcalf
In reply to this post by Peng Yu

On Wednesday, 3 July, 2019 11:59, Peng Yu <[hidden email]> wrote:

>As I said in my original message "I am trying to understand how lock
>is implemented in sqlite3".

from os_unix.c:

  /* The following describes the implementation of the various locks and
  ** lock transitions in terms of the POSIX advisory shared and exclusive
  ** lock primitives (called read-locks and write-locks below, to avoid
  ** confusion with SQLite lock names). The algorithms are complicated
  ** slightly in order to be compatible with Windows95 systems simultaneously
  ** accessing the same database file, in case that is ever required.
  **
  ** Symbols defined in os.h indentify the 'pending byte' and the 'reserved
  ** byte', each single bytes at well known offsets, and the 'shared byte
  ** range', a range of 510 bytes at a well known offset.
  **
  ** To obtain a SHARED lock, a read-lock is obtained on the 'pending
  ** byte'.  If this is successful, 'shared byte range' is read-locked
  ** and the lock on the 'pending byte' released.  (Legacy note:  When
  ** SQLite was first developed, Windows95 systems were still very common,
  ** and Widnows95 lacks a shared-lock capability.  So on Windows95, a
  ** single randomly selected by from the 'shared byte range' is locked.
  ** Windows95 is now pretty much extinct, but this work-around for the
  ** lack of shared-locks on Windows95 lives on, for backwards
  ** compatibility.)
  **
  ** A process may only obtain a RESERVED lock after it has a SHARED lock.
  ** A RESERVED lock is implemented by grabbing a write-lock on the
  ** 'reserved byte'.
  **
  ** A process may only obtain a PENDING lock after it has obtained a
  ** SHARED lock. A PENDING lock is implemented by obtaining a write-lock
  ** on the 'pending byte'. This ensures that no new SHARED locks can be
  ** obtained, but existing SHARED locks are allowed to persist. A process
  ** does not have to obtain a RESERVED lock on the way to a PENDING lock.
  ** This property is used by the algorithm for rolling back a journal file
  ** after a crash.
  **
  ** An EXCLUSIVE lock, obtained after a PENDING lock is held, is
  ** implemented by obtaining a write-lock on the entire 'shared byte
  ** range'. Since all other locks require a read-lock on one of the bytes
  ** within this range, this ensures that no other locks are held on the
  ** database.
  */

So the original advise to read the os.c/os.h, os_common.h, os_unix.c and os_win.c/os_win.h was valid.  Only knowing how to read English prose is required.

note:
/os.h indentify/os.h identify/
/Widnows95/Windows95/
/selected by from/selected byte from/

--
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.




_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How lock is implemented upon write?

Peng Yu
Something in a higher level language (e.g., Python) that is easy to
run maybe better. Or at least some stand-alone C code (compilable to
executables) that is solely for the purpose of demonstrating the
locking mechanism. The descriptions in os_unix.c don't satisfy these
conditions. Just based on them, it is hard for me to make my own
toying implementation on the locking mechanism to understand the nuts
and bolts.

On 7/3/19, Keith Medcalf <[hidden email]> wrote:

>
> On Wednesday, 3 July, 2019 11:59, Peng Yu <[hidden email]> wrote:
>
>>As I said in my original message "I am trying to understand how lock
>>is implemented in sqlite3".
>
> from os_unix.c:
>
>   /* The following describes the implementation of the various locks and
>   ** lock transitions in terms of the POSIX advisory shared and exclusive
>   ** lock primitives (called read-locks and write-locks below, to avoid
>   ** confusion with SQLite lock names). The algorithms are complicated
>   ** slightly in order to be compatible with Windows95 systems
> simultaneously
>   ** accessing the same database file, in case that is ever required.
>   **
>   ** Symbols defined in os.h indentify the 'pending byte' and the 'reserved
>   ** byte', each single bytes at well known offsets, and the 'shared byte
>   ** range', a range of 510 bytes at a well known offset.
>   **
>   ** To obtain a SHARED lock, a read-lock is obtained on the 'pending
>   ** byte'.  If this is successful, 'shared byte range' is read-locked
>   ** and the lock on the 'pending byte' released.  (Legacy note:  When
>   ** SQLite was first developed, Windows95 systems were still very common,
>   ** and Widnows95 lacks a shared-lock capability.  So on Windows95, a
>   ** single randomly selected by from the 'shared byte range' is locked.
>   ** Windows95 is now pretty much extinct, but this work-around for the
>   ** lack of shared-locks on Windows95 lives on, for backwards
>   ** compatibility.)
>   **
>   ** A process may only obtain a RESERVED lock after it has a SHARED lock.
>   ** A RESERVED lock is implemented by grabbing a write-lock on the
>   ** 'reserved byte'.
>   **
>   ** A process may only obtain a PENDING lock after it has obtained a
>   ** SHARED lock. A PENDING lock is implemented by obtaining a write-lock
>   ** on the 'pending byte'. This ensures that no new SHARED locks can be
>   ** obtained, but existing SHARED locks are allowed to persist. A process
>   ** does not have to obtain a RESERVED lock on the way to a PENDING lock.
>   ** This property is used by the algorithm for rolling back a journal file
>   ** after a crash.
>   **
>   ** An EXCLUSIVE lock, obtained after a PENDING lock is held, is
>   ** implemented by obtaining a write-lock on the entire 'shared byte
>   ** range'. Since all other locks require a read-lock on one of the bytes
>   ** within this range, this ensures that no other locks are held on the
>   ** database.
>   */
>
> So the original advise to read the os.c/os.h, os_common.h, os_unix.c and
> os_win.c/os_win.h was valid.  Only knowing how to read English prose is
> required.
>
> note:
> /os.h indentify/os.h identify/
> /Widnows95/Windows95/
> /selected by from/selected byte from/
>
> --
> The fact that there's a Highway to Hell but only a Stairway to Heaven says a
> lot about anticipated traffic volume.
>
>
>
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>


--
Regards,
Peng
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How lock is implemented upon write?

Jens Alfke-2

> On Jul 3, 2019, at 6:20 PM, Peng Yu <[hidden email]> wrote:
>
> Something in a higher level language (e.g., Python) that is easy to
> run maybe better. Or at least some stand-alone C code (compilable to
> executables) that is solely for the purpose of demonstrating the
> locking mechanism.

After you figure it out, you should write that and contribute it to help others!

—Jens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How lock is implemented upon write?

Peng Yu
So the fundamental C API that unix_os.c is based on is the only
following but nothing else?

- fcntl: http://pubs.opengroup.org/onlinepubs/9699919799/functions/fcntl.html
- flock: https://www.freebsd.org/cgi/man.cgi?query=flock&sektion=2

On 7/3/19, Jens Alfke <[hidden email]> wrote:

>
>> On Jul 3, 2019, at 6:20 PM, Peng Yu <[hidden email]> wrote:
>>
>> Something in a higher level language (e.g., Python) that is easy to
>> run maybe better. Or at least some stand-alone C code (compilable to
>> executables) that is solely for the purpose of demonstrating the
>> locking mechanism.
>
> After you figure it out, you should write that and contribute it to help
> others!
>
> —Jens
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>


--
Regards,
Peng
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How lock is implemented upon write?

Larry Brasfield
In reply to this post by Peng Yu
Peng Yu wrote:
>> So the fundamental C API that unix_os.c is based on is
>> the only following but nothing else?
>>  [ followed by links to *nix C API fcntl(…) docs ]

The (C and fundamental) API you cite is the interface provided for applications running on Unix-like operating systems to lock files in various ways.  Applications can use that API if they can pass the right parameters to the OS-provided entry point using C calling convention.  This is but tangentially related to “how lock is implemented upon write”, presumably in SQLite, (the subject of this thread, I guess.)  I say “tangentially” because there is far more to SQLite’s database locking than managing an OS-provided file lock. I can see this at a glance by looking at fcnt() calls (or their macro stand-ins) in sqlite3.c .

You appear to want to understand SQLite implements locking, apparently without reading the (C) code which effects that behavior.  I am not surprised than nobody wants to recast all that logic for you into a language you are willing and/or able to read.  It is complex, and changes among the platforms targeted by SQLite.  And it hardly matters to most SQLite users *how* it is implemented; their concern is how it works, which is well documented (as others have mentioned), and that it works well and reliably.

I notice that you have ignored repeated requests for insight into why you have made your inquiry.  People who may be able to help you with your objective ask for such information because, often, that leads to or permits a more direct solution to your actual problem.  Certainly in this case, where the Pascal translation of many lines of C would take hours to generate, a more direct solution is probably going to be the only one likely to be offered.

Cheers,
-
Larry Brasfield
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How lock is implemented upon write?

Adrian Ho
On 5/7/19 3:14 AM, Larry Brasfield wrote:
> I notice that you have ignored repeated requests for insight into why
> you have made your inquiry. People who may be able to help you with
> your objective ask for such information because, often, that leads to
> or permits a more direct solution to your actual problem.
In fact, this phenomenon happens so often, it even has a Wikipedia
entry: https://en.wikipedia.org/wiki/XY_problem

It's surprisingly easy to build a consulting career around asking just
one question, "What problem *X* are you trying to solve, for which you
think this method *Y* is the (probably incorrect) solution?". The real
trick is to summon the patience to guide your clients through the
process of discovering *X*, because they're almost always fixated with *Y*.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How lock is implemented upon write?

Simon Slavin-3
Here's my guess.  OP is trying to implement locking in Python.  OP sees that SQLite does locking and wants to copy code.

Obviously, that's beyond the range of this mailing list, but just to be helpful, here's some stackoverflow:

<https://stackoverflow.com/questions/489861/locking-a-file-in-python#498505>

Be sure to read all the way down the comments before you start copying code.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How lock is implemented upon write?

Peng Yu
> Here's my guess.  OP is trying to implement locking in Python.  OP sees that
> SQLite does locking and wants to copy code.
>
> Obviously, that's beyond the range of this mailing list, but just to be
> helpful, here's some stackoverflow:
>
> <https://stackoverflow.com/questions/489861/locking-a-file-in-python#498505>

I don't think this implementation in Python is the same as that in
SQLite3. By default, it uses either a link or a directory to lock a
file.

https://github.com/pypa/pip/blob/master/src/pip/_vendor/lockfile/__init__.py#L340

if hasattr(os, "link"):
    from . import linklockfile as _llf
    LockFile = _llf.LinkLockFile
else:
    from . import mkdirlockfile as _mlf
    LockFile = _mlf.MkdirLockFile

FileLock = LockFile

There is something shown below that uses SQLite3, but it still does
not go deeper into reimplementing using the raw code available from
SQLite3. This implementation merely calls SQLite3.

https://github.com/pypa/pip/blob/master/src/pip/_vendor/lockfile/sqlitelockfile.py#L14

My take-home message from this code is that it might be difficult to
just extract the part from SQLite3 that is for file locking.
Otherwise, the author who wrote this piece of code probably should
have done so already. However, for more efficient file locking, I
think it probably makes sense to only extract the part for file
locking SQLite3 and remove other parts SQLite3 to reduce overhead.

--
Regards,
Peng
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How lock is implemented upon write?

Keith Medcalf

On Friday, 5 July, 2019 12:26, Peng Yu <[hidden email]>:

>There is something shown below that uses SQLite3, but it still does
>not go deeper into reimplementing using the raw code available from
>SQLite3. This implementation merely calls SQLite3.

>https://github.com/pypa/pip/blob/master/src/pip/_vendor/lockfile/sqlitelockfile.py#L14

>My take-home message from this code is that it might be difficult to
>just extract the part from SQLite3 that is for file locking.
>Otherwise, the author who wrote this piece of code probably should
>have done so already. However, for more efficient file locking, I
>think it probably makes sense to only extract the part for file
>locking SQLite3 and remove other parts SQLite3 to reduce overhead.

This does not implement SQLite3 locking.  It uses SQLite3 as a database in which to store information about that which is locked, and uses that database to implement a locking mechanism for other things.  It by happenstance uses an SQLite3 database to store the information, but it does not depend on it.  That is, the SQL would work against any database connection to an SQL database including SQL Server, DB2, or what have you.  (analogy:  A telephone book stores information about telephone numbers but does not implement a telephone).

In any event of the cause, the code is in error and will not work correctly (it is defective).  It also does not deal with race conditions very well.  

--
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.





_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: How lock is implemented upon write?

Jens Alfke-2
In reply to this post by Peng Yu

> On Jul 4, 2019, at 6:57 AM, Peng Yu <[hidden email]> wrote:
>
> So the fundamental C API that unix_os.c is based on is the only
> following but nothing else?
>
> - fcntl: http://pubs.opengroup.org/onlinepubs/9699919799/functions/fcntl.html
> - flock: https://www.freebsd.org/cgi/man.cgi?query=flock&sektion=2

I believe so. Bot more properly, those are _Unix_ APIs; not every OS has them. (I know very little about Windows, but from what I’ve heard, its filesystem semantics are quite different in some ways.)

If you want to know how to lock files on Unix, looking at SQLite is probably not the best thing to do, because SQLite has a lot of other complex things to do when it manages locks.

—Jens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users