view mercurial/thirdparty/xdiff/xutils.c @ 40626:87a872555e90

revlog: detect incomplete revlog reads

_readsegment() is supposed to return N bytes of revlog revision
data starting at a file offset. Surprisingly, its behavior before
this patch never verified that it actually read and returned N
bytes! Instead, it would perform the read(), then return whatever
data was available. And even more surprisingly, nothing in the
call chain appears to have been validating that it received all
the data it was expecting.

This behavior could lead to partial or incomplete revision chunks
being operated on. This could result in e.g. cached deltas being
applied against incomplete base revisions. The delta application
process would happily perform this operation. Only hash
verification would detect the corruption and save us.

This commit changes the behavior of raw revlog reading to validate
that we actually read() the number of bytes that were requested.
We will raise a more specific error faster, rather than possibly
have it go undetected or manifest later in the call stack, at
delta application or hash verification.

Differential Revision: https://phab.mercurial-scm.org/D5266

/*
 *  LibXDiff by Davide Libenzi ( File Differential Library )
 *  Copyright (C) 2003	Davide Libenzi
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2.1 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, see
 *  <http://www.gnu.org/licenses/>.
 *
 *  Davide Libenzi <[e-mail]>
 *
 */

#include <limits.h>
#include <assert.h>
#include "xinclude.h"




int64_t xdl_bogosqrt(int64_t n) {
	int64_t i;

	/*
	 * Classical integer square root approximation using shifts.
	 */
	for (i = 1; n > 0; n >>= 2)
		i <<= 1;

	return i;
}


void *xdl_mmfile_first(mmfile_t *mmf, int64_t *size)
{
	*size = mmf->size;
	return mmf->ptr;
}


int64_t xdl_mmfile_size(mmfile_t *mmf)
{
	return mmf->size;
}


int xdl_cha_init(chastore_t *cha, int64_t isize, int64_t icount) {

	cha->head = cha->tail = NULL;
	cha->isize = isize;
	cha->nsize = icount * isize;
	cha->ancur = cha->sncur = NULL;
	cha->scurr = 0;

	return 0;
}


void xdl_cha_free(chastore_t *cha) {
	chanode_t *cur, *tmp;

	for (cur = cha->head; (tmp = cur) != NULL;) {
		cur = cur->next;
		xdl_free(tmp);
	}
}


void *xdl_cha_alloc(chastore_t *cha) {
	chanode_t *ancur;
	void *data;

	if (!(ancur = cha->ancur) || ancur->icurr == cha->nsize) {
		if (!(ancur = (chanode_t *) xdl_malloc(sizeof(chanode_t) + cha->nsize))) {

			return NULL;
		}
		ancur->icurr = 0;
		ancur->next = NULL;
		if (cha->tail)
			cha->tail->next = ancur;
		if (!cha->head)
			cha->head = ancur;
		cha->tail = ancur;
		cha->ancur = ancur;
	}

	data = (char *) ancur + sizeof(chanode_t) + ancur->icurr;
	ancur->icurr += cha->isize;

	return data;
}

int64_t xdl_guess_lines(mmfile_t *mf, int64_t sample) {
	int64_t nl = 0, size, tsize = 0;
	char const *data, *cur, *top;

	if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) {
		for (top = data + size; nl < sample && cur < top; ) {
			nl++;
			if (!(cur = memchr(cur, '\n', top - cur)))
				cur = top;
			else
				cur++;
		}
		tsize += (long) (cur - data);
	}

	if (nl && tsize)
		nl = xdl_mmfile_size(mf) / (tsize / nl);

	return nl + 1;
}

int xdl_recmatch(const char *l1, int64_t s1, const char *l2, int64_t s2)
{
	if (s1 == s2 && !memcmp(l1, l2, s1))
		return 1;
	return 0;
}

uint64_t xdl_hash_record(char const **data, char const *top) {
	uint64_t ha = 5381;
	char const *ptr = *data;

	for (; ptr < top && *ptr != '\n'; ptr++) {
		ha += (ha << 5);
		ha ^= (unsigned long) *ptr;
	}
	*data = ptr < top ? ptr + 1: ptr;

	return ha;
}

unsigned int xdl_hashbits(int64_t size) {
	int64_t val = 1;
	unsigned int bits = 0;

	for (; val < size && bits < (int64_t) CHAR_BIT * sizeof(unsigned int); val <<= 1, bits++);
	return bits ? bits: 1;
}