This is an archive of the discontinued Mercurial Phabricator instance.

Differential D5438

rust-cpython: implementing Graph using C parents function
ClosedPublic

Authored by gracinet on Dec 15 2018, 6:42 AM.

Download Raw Diff

Details

Reviewers

None

Group Reviewers

hg-reviewers

Commits

rHG4c25038c112c: rust-cpython: implement Graph using C parents function

Summary

We introduce the Index struct that wraps the C index. It is
not intrinsically protected by the GIL (see the lengthy
discussion in its docstring). Improving on this seems
prematurate at this point.

A pointer to the parents function is stored on the parsers
C extension module as a capsule object.

This is the recommended way to export a C API for consumption
from other extensions.
See also: https://docs.python.org/2.7/c-api/capsule.html

In our case, we use it in cindex.rs, retrieving function
pointer from the capsule and storing it within the CIndex
struct, alongside with a pointer to the index. From there,
the implementation is very close to the one from hg-direct-ffi.

The naming convention for the capsule is inspired from the
one in datetime:

>>> import datetime
>>> datetime.datetime_CAPI
<capsule object "datetime.datetime_CAPI" at 0x7fb51201ecf0>

although in datetime's case, the capsule points to a struct holding
several type objects and methods.

Diff Detail

Repository

rHG Mercurial

Lint

Automatic diff as part of commit; lint not applicable.

Unit

Automatic diff as part of commit; unit tests not applicable.

Event Timeline

gracinet created this revision.Dec 15 2018, 6:42 AM

Herald added a reviewer: hg-reviewers. · View Herald TranscriptDec 15 2018, 6:42 AM

Herald added subscribers: mercurial-devel, kevincox, durin42. · View Herald Transcript

gracinet added a child revision: D5439: rust-cpython: binding for AncestorsIterator.Dec 15 2018, 6:42 AM

Here, I'd be tempted to submit a py_capsule_fn macro to rust-cpython, but I guess it can wait.

+type IndexParentsFn = unsafe extern "C" fn(
+ index: *mut python_sys::PyObject,
+ rev: ssize_t,
+ ps: *mut [c_int; 2],
+ max_rev: c_int,
+) -> c_int;

The type differs from the private function. It's
int HgRevlogIndex_GetParents(PyObject *op, int rev, int *ps).

+impl Graph for Index {
+ /// wrap a call to the C extern parents function
+ fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
+ let mut res: [c_int; 2] = [0; 2];
+ let code = unsafe {
+ (self.parents)(
+ self.index.as_ptr(),
+ rev as ssize_t,
+ &mut res as *mut [c_int; 2],
+ rev,
+ )
+ };
+ match code {
+ 0 => Ok(res),
+ _ => Err(GraphError::ParentOutOfRange(rev)),
+ }

I think Python<'p> is needed here to make it safe, but I have no idea how
to express that clearly. Do we need a wrapper that implements Graph and
translates Graph::parents(rev) to Index::parents(py, rev)?

a/mercurial/cext/revlog.c

+++ b/mercurial/cext/revlog.c
@@ -2878,6 +2878,12 @@
	if (nullentry)
		PyObject_GC_UnTrack(nullentry);
+ void *caps = PyCapsule_New(

Please move void *caps to top. We still need to conform to C89.

@yuja yes sorry, forgot to adapt to the new signature. That'll be fixed in next version, and in revlog.c, the capsule pointer declaration is now at the top.

About protecting parents() with the GIL Python<'p>, I'll have to think more about it, but the solution that comes to mind is as you suggest a two-step wrapping: the long lived Index would wrap the actual index object and the function pointer retrieved from the capsule, but would not implement the Graph trait directly. A shorter term GILProtectedIndex would then implement the Graph trait by wrapping the Index together with the Python<'p> marker coming from a call to the Python interface (methods of the py_class! of this series), hence forbidding to release the GIL from any code that calls Graph::parents(). I think the current usage is safe, though, because our Python interface methods don't release the GIL, but it's true the Index isn't inherentrly safe.

A simpler possibility would be to go the other way: release the GIL from the Python interface methods, and reacquire it at each call of Graph::parents. I don't know what the overhead would be, especially with Mercurial being currently monothreaded (unless I'm mistaken), meaning that we don't have benefits to reap. Maybe I'll try that one, since it's so simple, and if I measure negligible overhead, I'll go for it.

As a side note, the same problem could arise with the direct-ffi bindings: the safety promise is held by the caller, this time from C code.

I gave the solution to reacquire the GIL explicitely from Index a quick try, without even releasing it from the callers (which is ok according to https://docs.python.org/2.7/c-api/init.html#c.PyGILState_Ensure), and it is more than a 20% penalty.

I'm measuring with hg perfancestors on mozilla-central, here are the medians of wall time

pure Python: 0.295
Rust cpython (unmodified): 0.101
Rust direct-ffi: 0.092
Rust cpython reacquiring the GIL: 0.124

About protecting parents() with the GIL `Python<'p>`, I'll have to think more about it, but the solution that comes to mind is as you suggest a two-step wrapping: the long lived `Index` would wrap the actual index object and the function pointer retrieved from the capsule, but would not implement the `Graph` trait directly. A shorter term `GILProtectedIndex` would then implement the `Graph` trait by wrapping the `Index` together with the `Python<'p>` marker coming from a call to the Python interface (methods of the `py_class!` of this series), hence forbidding to release the GIL from any code that calls `Graph::parents()`. I think the current usage is safe, though, because our Python interface methods don't release the GIL, but it's true the `Index` isn't inherentrly safe.

Actually I like this idea since it will be a step forward to wrap the Index
object properly as a PyObject.

A simpler possibility would be to go the other way: release the GIL from the Python interface methods, and reacquire it at each call of `Graph::parents`. I don't know what the overhead would be, especially with Mercurial being currently monothreaded (unless I'm mistaken), meaning that we don't have benefits to reap. Maybe I'll try that one, since it's so simple, and if I measure negligible overhead, I'll go for it.
As a side note, the same problem could arise with the direct-ffi bindings: the safety promise is held by the caller, this time from C code.

Yes. The current code is safe unless we do invoke it with e.g.
py.allow_threads(), and I'm not so afraid of leaving the issue as TODO.

gracinet edited the summary of this revision. (Show Details)Dec 22 2018, 11:23 AM

gracinet updated this revision to Diff 12949.

Closed by commit rHG4c25038c112c: rust-cpython: implement Graph using C parents function (authored by gracinet). · Explain WhyDec 24 2018, 12:00 AM

This revision was automatically updated to reflect the committed changes.

+/ # TODO find a solution to make it GIL safe again.
+/
+/ This is non trivial, and can wait until we have a clearer picture with
+/ more Rust Mercurial constructs.
+/
+/ One possibility would be to a GILProtectedIndex wrapper enclosing
+/ a Python<'p> marker and have it be the one implementing the
+/ Graph trait, but this would mean the Graph implementor would become
+/ likely to change between subsequent method invocations of the hg-core
+/ objects (a serious change of the hg-core API):
+/ either exposing ways to mutate the Graph, or making it a non persistent
+/ parameter in the relevant methods that need one.

Thinking this a bit further, I'm getting to feel that a "non persistent
parameter" will be an easier choice.

If an Index object were implemented in pure Rust, it would hold the entire
index data in memory. As we wouldn't want to memcpy such large object, there
would be some reference types (e.g. &Index, Rc<Index>, etc.) involved
somewhere. For instance, AncestorsIterator<G> might have to be
AncestorsIterator<G: 'g>, and holding a reference would slightly complicate
things in a similar way to holding Python<'p>.

Index could be backed by e.g. Rc<RefCell<_>> to allow any objects to own
<G: Index> copies, but I don't feel like this is a good design.

@yuja, thanks for the queueing !

Index could be backed by e.g. Rc<RefCell<_>> to allow any objects to own
<G: Index> copies, but I don't feel like this is a good design.

If we want one day to have Mercurial work in a multi-threaded way, I guess that something like Arc<RWLock<_>> would be about necessary for an index implemented in Rust. But anyway, we are thinking alike.

Revision Contents
Changeset List

		Path
M		mercurial/cext/revlog.c (7 lines)
A	M	rust/hg-cpython/src/cindex.rs (121 lines)
M		rust/hg-cpython/src/lib.rs (2 lines)

Diff	ID	Description	Created	Lint	Unit
Base		Base
Diff 1	12875		Dec 15 2018, 6:42 AM	★	★
Diff 2	12949		Dec 22 2018, 11:23 AM	★	★
Diff 3	12967	rHG4c25038c112cfca2de659463ffb45ef9c13088f6	Dec 3 2018, 1:44 AM	★	★

Status	Author	Revision
Abandoned	gracinet	D5443 ancestor: uniformity of calling lazyancestors classes
Closed	gracinet	D5442 rust-cpython: using the new bindings from Python
Closed	gracinet	D5441 rust-cpython: binding for LazyAncestors
Closed	gracinet	D5440 rust: core implementation for lazyancestors
Closed	gracinet	D5439 rust-cpython: binding for AncestorsIterator
Closed	gracinet	D5438 rust-cpython: implementing Graph using C parents function
Closed	gracinet	D5437 rust-cpython: testing the bindings from Python
Closed	gracinet	D5436 rust-cpython: build via HGWITHRUSTEXT=cpython
Closed	gracinet	D5435 rust: better treatment of cargo/rustc errors
Closed	gracinet	D5434 rust-cpython: started cpython crate bindings
Closed	gracinet	D5433 rust-cpython: excluded hgcli from workspace

Diff 12967

mercurial/cext/revlog.c

	0, /* tp_dictoffset */			0, /* tp_dictoffset */
	(initproc)rustla_init, /* tp_init */			(initproc)rustla_init, /* tp_init */
	0, /* tp_alloc */			0, /* tp_alloc */
	};			};
	#endif /* WITH_RUST */			#endif /* WITH_RUST */

	void revlog_module_init(PyObject *mod)			void revlog_module_init(PyObject *mod)
	{			{
				PyObject *caps = NULL;
	HgRevlogIndex_Type.tp_new = PyType_GenericNew;			HgRevlogIndex_Type.tp_new = PyType_GenericNew;
	if (PyType_Ready(&HgRevlogIndex_Type) < 0)			if (PyType_Ready(&HgRevlogIndex_Type) < 0)
	return;			return;
	Py_INCREF(&HgRevlogIndex_Type);			Py_INCREF(&HgRevlogIndex_Type);
	PyModule_AddObject(mod, "index", (PyObject *)&HgRevlogIndex_Type);			PyModule_AddObject(mod, "index", (PyObject *)&HgRevlogIndex_Type);

	nodetreeType.tp_new = PyType_GenericNew;			nodetreeType.tp_new = PyType_GenericNew;
	if (PyType_Ready(&nodetreeType) < 0)			if (PyType_Ready(&nodetreeType) < 0)
	return;			return;
	Py_INCREF(&nodetreeType);			Py_INCREF(&nodetreeType);
	PyModule_AddObject(mod, "nodetree", (PyObject *)&nodetreeType);			PyModule_AddObject(mod, "nodetree", (PyObject *)&nodetreeType);

	if (!nullentry) {			if (!nullentry) {
	nullentry = Py_BuildValue(PY23("iiiiiiis#", "iiiiiiiy#"), 0, 0,			nullentry = Py_BuildValue(PY23("iiiiiiis#", "iiiiiiiy#"), 0, 0,
	0, -1, -1, -1, -1, nullid, 20);			0, -1, -1, -1, -1, nullid, 20);
	}			}
	if (nullentry)			if (nullentry)
	PyObject_GC_UnTrack(nullentry);			PyObject_GC_UnTrack(nullentry);

				caps = PyCapsule_New(HgRevlogIndex_GetParents,
				"mercurial.cext.parsers.index_get_parents_CAPI",
				NULL);
				if (caps != NULL)
				PyModule_AddObject(mod, "index_get_parents_CAPI", caps);

	#ifdef WITH_RUST			#ifdef WITH_RUST
	rustlazyancestorsType.tp_new = PyType_GenericNew;			rustlazyancestorsType.tp_new = PyType_GenericNew;
	if (PyType_Ready(&rustlazyancestorsType) < 0)			if (PyType_Ready(&rustlazyancestorsType) < 0)
	return;			return;
	Py_INCREF(&rustlazyancestorsType);			Py_INCREF(&rustlazyancestorsType);
	PyModule_AddObject(mod, "rustlazyancestors",			PyModule_AddObject(mod, "rustlazyancestors",
	(PyObject *)&rustlazyancestorsType);			(PyObject *)&rustlazyancestorsType);
	#endif			#endif
	}			}

rust/hg-cpython/src/cindex.rs

This file was added.

				// cindex.rs
				//
				// Copyright 2018 Georges Racinet <gracinet@anybox.fr>
				//
				// This software may be used and distributed according to the terms of the
				// GNU General Public License version 2 or any later version.

				//! Bindings to use the Index defined by the parsers C extension
				//!
				//! Ideally, we should use an Index entirely implemented in Rust,
				//! but this will take some time to get there.
				#[cfg(feature = "python27")]
				extern crate python27_sys as python_sys;
				#[cfg(feature = "python3")]
				extern crate python3_sys as python_sys;

				use self::python_sys::PyCapsule_Import;
				use cpython::{PyErr, PyObject, PyResult, Python};
				use hg::{Graph, GraphError, Revision};
				use libc::c_int;
				use std::ffi::CStr;
				use std::mem::transmute;

				type IndexParentsFn = unsafe extern "C" fn(
				index: *mut python_sys::PyObject,
				rev: c_int,
				ps: *mut [c_int; 2],
				) -> c_int;

				/// A `Graph` backed up by objects and functions from revlog.c
				///
				/// This implementation of the `Graph` trait, relies on (pointers to)
				/// - the C index object (`index` member)
				/// - the `index_get_parents()` function (`parents` member)
				///
				/// # Safety
				///
				/// The C index itself is mutable, and this Rust exposition is **not
				/// protected by the GIL**, meaning that this construct isn't safe with respect
				/// to Python threads.
				///
				/// All callers of this `Index` must acquire the GIL and must not release it
				/// while working.
				///
				/// # TODO find a solution to make it GIL safe again.
				///
				/// This is non trivial, and can wait until we have a clearer picture with
				/// more Rust Mercurial constructs.
				///
				/// One possibility would be to a `GILProtectedIndex` wrapper enclosing
				/// a `Python<'p>` marker and have it be the one implementing the
				/// `Graph` trait, but this would mean the `Graph` implementor would become
				/// likely to change between subsequent method invocations of the `hg-core`
				/// objects (a serious change of the `hg-core` API):
				/// either exposing ways to mutate the `Graph`, or making it a non persistent
				/// parameter in the relevant methods that need one.
				///
				/// Another possibility would be to introduce an abstract lock handle into
				/// the core API, that would be tied to `GILGuard` / `Python<'p>`
				/// in the case of the `cpython` crate bindings yet could leave room for other
				/// mechanisms in other contexts.

				pub struct Index {
				index: PyObject,
				parents: IndexParentsFn,
				}

				impl Index {
				pub fn new(py: Python, index: PyObject) -> PyResult<Self> {
				Ok(Index {
				index: index,
				parents: decapsule_parents_fn(py)?,
				})
				}
				}

				impl Graph for Index {
				/// wrap a call to the C extern parents function
				fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
				let mut res: [c_int; 2] = [0; 2];
				let code = unsafe {
				(self.parents)(
				self.index.as_ptr(),
				rev as c_int,
				&mut res as *mut [c_int; 2],
				)
				};
				match code {
				0 => Ok(res),
				_ => Err(GraphError::ParentOutOfRange(rev)),
				}
				}
				}

				/// Return the `index_get_parents` function of the parsers C Extension module.
				///
				/// A pointer to the function is stored in the `parsers` module as a
				/// standard [Python capsule](https://docs.python.org/2/c-api/capsule.html).
				///
				/// This function retrieves the capsule and casts the function pointer
				///
				/// Casting function pointers is one of the rare cases of
				/// legitimate use cases of `mem::transmute()` (see
				/// https://doc.rust-lang.org/std/mem/fn.transmute.html of
				/// `mem::transmute()`.
				/// It is inappropriate for architectures where
				/// function and data pointer sizes differ (so-called "Harvard
				/// architectures"), but these are nowadays mostly DSPs
				/// and microcontrollers, hence out of our scope.
				fn decapsule_parents_fn(py: Python) -> PyResult<IndexParentsFn> {
				unsafe {
				let caps_name = CStr::from_bytes_with_nul_unchecked(
				b"mercurial.cext.parsers.index_get_parents_CAPI\0",
				);
				let from_caps = PyCapsule_Import(caps_name.as_ptr(), 0);
				if from_caps.is_null() {
				return Err(PyErr::fetch(py));
				}
				Ok(transmute(from_caps))
				}
				}

rust/hg-cpython/src/lib.rs

	//! >>> from mercurial.rustext import ancestor			//! >>> from mercurial.rustext import ancestor
	//! >>> ancestor.__doc__			//! >>> ancestor.__doc__
	//! 'Generic DAG ancestor algorithms - Rust implementation'			//! 'Generic DAG ancestor algorithms - Rust implementation'
	//! ```			//! ```

	#[macro_use]			#[macro_use]
	extern crate cpython;			extern crate cpython;
	extern crate hg;			extern crate hg;
				extern crate libc;

	mod ancestors;			mod ancestors;
				mod cindex;
	mod exceptions;			mod exceptions;

	py_module_initializer!(rustext, initrustext, PyInit_rustext, \|py, m\| {			py_module_initializer!(rustext, initrustext, PyInit_rustext, \|py, m\| {
	m.add(			m.add(
	py,			py,
	"__doc__",			"__doc__",
	"Mercurial core concepts - Rust implementation",			"Mercurial core concepts - Rust implementation",
	)?;			)?;

	let dotted_name: String = m.get(py, "__name__")?.extract(py)?;			let dotted_name: String = m.get(py, "__name__")?.extract(py)?;
	m.add(py, "__package__", "mercurial")?;			m.add(py, "__package__", "mercurial")?;
	m.add(py, "ancestor", ancestors::init_module(py, &dotted_name)?)?;			m.add(py, "ancestor", ancestors::init_module(py, &dotted_name)?)?;
	m.add(py, "GraphError", py.get_type::<exceptions::GraphError>())?;			m.add(py, "GraphError", py.get_type::<exceptions::GraphError>())?;
	Ok(())			Ok(())
	});			});