This is an archive of the discontinued Mercurial Phabricator instance.

Differential D4108

index: extract a type for the nodetree
ClosedPublic

Authored by martinvonz on Aug 5 2018, 3:58 AM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHGd1bc0e7c862b: index: extract a type for the nodetree
Summary

This is a first step towards exposing the nodetree as a Python type.

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

martinvonz created this revision.Aug 5 2018, 3:58 AM
yuja added a subscriber: yuja.Aug 6 2018, 9:10 AM

Queued, but there seem to be a couple of minor errors. Can you fix them
if they remain in the code after the refactor?

static int nt_new(indexObject *self)
{

	if (self->ntlength == self->ntcapacity) {
  • if (self->ntcapacity >= INT_MAX / (sizeof(nodetree) * 2)) {

+ if (self->ntcapacity >= INT_MAX / (sizeof(nodetreenode) * 2)) {

			PyErr_SetString(PyExc_MemoryError,
					"overflow in nt_new");
			return -1;
		}
		self->ntcapacity *= 2;
  • self->nt = realloc(self->nt,
  • self->ntcapacity * sizeof(nodetree));
  • if (self->nt == NULL) {

+ self->nt->nodes = realloc(self->nt->nodes,
+ self->ntcapacity * sizeof(nodetreenode));
+ if (self->nt->nodes == NULL) {

			PyErr_SetString(PyExc_MemoryError, "out of memory");
			return -1;

Need to free and nullify self->nt here?
Leaving self->nt && !self->nt->nodes state will probably lead to SEVG.

Another option is to leave ntcapacity and nodes unmodified on realloc
failure.

static int nt_init(indexObject *self)
{

	if (self->nt == NULL) {
  • if ((size_t)self->raw_length > INT_MAX / sizeof(nodetree)) {

+ self->nt = PyMem_Malloc(sizeof(nodetree));

PyMem_Malloc() and PyMem_Free() should be paired.

+ if ((size_t)self->raw_length > INT_MAX / sizeof(nodetreenode)) {

			PyErr_SetString(PyExc_ValueError, "overflow in nt_init");

Need to free and nullify self->nt here?

Closed by commit rHGd1bc0e7c862b: index: extract a type for the nodetree (authored by martinvonz). · Explain WhyAug 6 2018, 9:13 AM
This revision was automatically updated to reflect the committed changes.
indygreg added a subscriber: indygreg.Aug 6 2018, 4:11 PM

For the record, I'm not thrilled about queuing C code with known bugs.

yuja added a comment.Aug 7 2018, 10:03 AM
For the record, I'm not thrilled about queuing C code with known bugs.

Me neither. If there weren't unmanageable number of patches, I wouldn't
queue.

The fixes are pushed as 05c1f5f49ebb, f7d8fb2ed8a8, and dcd395dc98d8. Thanks.

Revision Contents
Changeset List

PathPackages
Mmercurial/cext/revlog.c (51 lines)

Diff 9972

mercurial/cext/revlog.c

* supported and proper types are used in the extensions themselves. */ * supported and proper types are used in the extensions themselves. */
#define PyInt_Check PyLong_Check #define PyInt_Check PyLong_Check
#define PyInt_FromLong PyLong_FromLong #define PyInt_FromLong PyLong_FromLong
#define PyInt_FromSsize_t PyLong_FromSsize_t #define PyInt_FromSsize_t PyLong_FromSsize_t
#define PyInt_AS_LONG PyLong_AS_LONG #define PyInt_AS_LONG PyLong_AS_LONG
#define PyInt_AsLong PyLong_AsLong #define PyInt_AsLong PyLong_AsLong
#endif #endif
typedef struct {
int children[16];
} nodetreenode;
/* /*
* A base-16 trie for fast node->rev mapping. * A base-16 trie for fast node->rev mapping.
* *
* Positive value is index of the next node in the trie * Positive value is index of the next node in the trie
* Negative value is a leaf: -(rev + 2) * Negative value is a leaf: -(rev + 2)
* Zero is empty * Zero is empty
*/ */
typedef struct { typedef struct {
int children[16]; nodetreenode *nodes;
} nodetree; } nodetree;
/* /*
* This class has two behaviors. * This class has two behaviors.
* *
* When used in a list-like way (with integer keys), we decode an * When used in a list-like way (with integer keys), we decode an
* entry in a RevlogNG index file on demand. Our last entry is a * entry in a RevlogNG index file on demand. Our last entry is a
* sentinel, always a nullid. We have limited support for * sentinel, always a nullid. We have limited support for
Py_CLEAR(self->cache[i]); Py_CLEAR(self->cache[i]);
free(self->cache); free(self->cache);
self->cache = NULL; self->cache = NULL;
} }
if (self->offsets) { if (self->offsets) {
PyMem_Free(self->offsets); PyMem_Free(self->offsets);
self->offsets = NULL; self->offsets = NULL;
} }
if (self->nt != NULL) {
free(self->nt->nodes);
free(self->nt); free(self->nt);
}
self->nt = NULL; self->nt = NULL;
Py_CLEAR(self->headrevs); Py_CLEAR(self->headrevs);
} }
static PyObject *index_clearcaches(indexObject *self) static PyObject *index_clearcaches(indexObject *self)
{ {
_index_clearcaches(self); _index_clearcaches(self);
self->ntlength = self->ntcapacity = 0; self->ntlength = self->ntcapacity = 0;
if (hex) if (hex)
maxlevel = nodelen > 40 ? 40 : (int)nodelen; maxlevel = nodelen > 40 ? 40 : (int)nodelen;
else else
maxlevel = nodelen > 20 ? 40 : ((int)nodelen * 2); maxlevel = nodelen > 20 ? 40 : ((int)nodelen * 2);
for (level = off = 0; level < maxlevel; level++) { for (level = off = 0; level < maxlevel; level++) {
int k = getnybble(node, level); int k = getnybble(node, level);
nodetree *n = &self->nt[off]; nodetreenode *n = &self->nt->nodes[off];
int v = n->children[k]; int v = n->children[k];
if (v < 0) { if (v < 0) {
const char *n; const char *n;
Py_ssize_t i; Py_ssize_t i;
v = -(v + 2); v = -(v + 2);
n = index_node(self, v); n = index_node(self, v);
} }
/* multiple matches against an ambiguous prefix */ /* multiple matches against an ambiguous prefix */
return -4; return -4;
} }
static int nt_new(indexObject *self) static int nt_new(indexObject *self)
{ {
if (self->ntlength == self->ntcapacity) { if (self->ntlength == self->ntcapacity) {
if (self->ntcapacity >= INT_MAX / (sizeof(nodetree) * 2)) { if (self->ntcapacity >= INT_MAX / (sizeof(nodetreenode) * 2)) {
PyErr_SetString(PyExc_MemoryError, PyErr_SetString(PyExc_MemoryError,
"overflow in nt_new"); "overflow in nt_new");
return -1; return -1;
} }
self->ntcapacity *= 2; self->ntcapacity *= 2;
self->nt = realloc(self->nt, self->nt->nodes = realloc(self->nt->nodes,
self->ntcapacity * sizeof(nodetree)); self->ntcapacity * sizeof(nodetreenode));
if (self->nt == NULL) { if (self->nt->nodes == NULL) {
PyErr_SetString(PyExc_MemoryError, "out of memory"); PyErr_SetString(PyExc_MemoryError, "out of memory");
return -1; return -1;
} }
memset(&self->nt[self->ntlength], 0, memset(&self->nt->nodes[self->ntlength], 0,
sizeof(nodetree) * (self->ntcapacity - self->ntlength)); sizeof(nodetreenode) * (self->ntcapacity - self->ntlength));
} }
return self->ntlength++; return self->ntlength++;
} }
static int nt_insert(indexObject *self, const char *node, int rev) static int nt_insert(indexObject *self, const char *node, int rev)
{ {
int level = 0; int level = 0;
int off = 0; int off = 0;
while (level < 40) { while (level < 40) {
int k = nt_level(node, level); int k = nt_level(node, level);
nodetree *n; nodetreenode *n;
int v; int v;
n = &self->nt[off]; n = &self->nt->nodes[off];
v = n->children[k]; v = n->children[k];
if (v == 0) { if (v == 0) {
n->children[k] = -rev - 2; n->children[k] = -rev - 2;
return 0; return 0;
} }
if (v < 0) { if (v < 0) {
const char *oldnode = index_node_existing(self, -(v + 2)); const char *oldnode = index_node_existing(self, -(v + 2));
int noff; int noff;
if (oldnode == NULL) if (oldnode == NULL)
return -1; return -1;
if (!memcmp(oldnode, node, 20)) { if (!memcmp(oldnode, node, 20)) {
n->children[k] = -rev - 2; n->children[k] = -rev - 2;
return 0; return 0;
} }
noff = nt_new(self); noff = nt_new(self);
if (noff == -1) if (noff == -1)
return -1; return -1;
/* self->nt may have been changed by realloc */ /* self->nt->nodes may have been changed by realloc */
self->nt[off].children[k] = noff; self->nt->nodes[off].children[k] = noff;
off = noff; off = noff;
n = &self->nt[off]; n = &self->nt->nodes[off];
n->children[nt_level(oldnode, ++level)] = v; n->children[nt_level(oldnode, ++level)] = v;
if (level > self->ntdepth) if (level > self->ntdepth)
self->ntdepth = level; self->ntdepth = level;
self->ntsplits += 1; self->ntsplits += 1;
} else { } else {
level += 1; level += 1;
off = v; off = v;
} }
} }
return -1; return -1;
} }
static int nt_delete_node(indexObject *self, const char *node) static int nt_delete_node(indexObject *self, const char *node)
{ {
/* rev==-2 happens to get encoded as 0, which is interpreted as not set */ /* rev==-2 happens to get encoded as 0, which is interpreted as not set */
return nt_insert(self, node, -2); return nt_insert(self, node, -2);
} }
static int nt_init(indexObject *self) static int nt_init(indexObject *self)
{ {
if (self->nt == NULL) { if (self->nt == NULL) {
if ((size_t)self->raw_length > INT_MAX / sizeof(nodetree)) { self->nt = PyMem_Malloc(sizeof(nodetree));
if (self->nt == NULL) {
PyErr_NoMemory();
return -1;
}
if ((size_t)self->raw_length > INT_MAX / sizeof(nodetreenode)) {
PyErr_SetString(PyExc_ValueError, "overflow in nt_init"); PyErr_SetString(PyExc_ValueError, "overflow in nt_init");
return -1; return -1;
} }
self->ntcapacity = self->raw_length < 4 self->ntcapacity = self->raw_length < 4
? 4 : (int)self->raw_length / 2; ? 4 : (int)self->raw_length / 2;
self->nt = calloc(self->ntcapacity, sizeof(nodetree)); self->nt->nodes = calloc(self->ntcapacity, sizeof(nodetreenode));
if (self->nt == NULL) { if (self->nt->nodes == NULL) {
free(self->nt);
self->nt = NULL;
PyErr_NoMemory(); PyErr_NoMemory();
return -1; return -1;
} }
self->ntlength = 1; self->ntlength = 1;
self->ntrev = (int)index_length(self); self->ntrev = (int)index_length(self);
self->ntlookups = 1; self->ntlookups = 1;
self->ntmisses = 0; self->ntmisses = 0;
if (nt_insert(self, nullid, -1) == -1) { if (nt_insert(self, nullid, -1) == -1) {
free(self->nt->nodes);
free(self->nt); free(self->nt);
self->nt = NULL; self->nt = NULL;
return -1; return -1;
} }
} }
return 0; return 0;
} }
* rest: length of shortest prefix * rest: length of shortest prefix
*/ */
static int nt_shortest(indexObject *self, const char *node) static int nt_shortest(indexObject *self, const char *node)
{ {
int level, off; int level, off;
for (level = off = 0; level < 40; level++) { for (level = off = 0; level < 40; level++) {
int k, v; int k, v;
nodetree *n = &self->nt[off]; nodetreenode *n = &self->nt->nodes[off];
k = nt_level(node, level); k = nt_level(node, level);
v = n->children[k]; v = n->children[k];
if (v < 0) { if (v < 0) {
const char *n; const char *n;
v = -(v + 2); v = -(v + 2);
n = index_node_existing(self, v); n = index_node_existing(self, v);
if (n == NULL) if (n == NULL)
return -3; return -3;