openbsd_malloc_linux.c

关于tor匿名通信的源代码

			    pf->next->page == ((caddr_t)pf->page + pf->size)) {
				/* And collapse the next too. */
				pt = pf->next;
				pf->size += pt->size;
				pf->next = pt->next;
				if (pf->next != NULL)
					pf->next->prev = pf;
			}
		} else if (pf->page == tail) {
			/* Prepend to entry. */
			cachesize -= pf->size;
			pf->size += l;
			pf->page = ptr;
			pf->pdir = spi;
		} else if (pf->next == NULL) {
			/* Append at tail of chain. */
			px->next = NULL;
			px->prev = pf;
			pf->next = px;
			pf = px;
			px = NULL;
		} else {
			wrterror("freelist is destroyed");
			errno = EFAULT;
			return;
		}
	}

	if (pf->pdir != last_dir) {
		prev_dir = last_dir;
		last_dir = pf->pdir;
	}

	/* Return something to OS ? */
	if (pf->size > (malloc_cache - cachesize)) {

		/*
		 * Keep the cache intact.  Notice that the '>' above guarantees that
		 * the pf will always have at least one page afterwards.
		 */
		if (munmap((char *) pf->page + (malloc_cache - cachesize),
		    pf->size - (malloc_cache - cachesize)) != 0)
			goto not_return;
		tail = (caddr_t)pf->page + pf->size;
		lidx = ptr2index(tail) - 1;
		pf->size = malloc_cache - cachesize;

		index = ptr2index((caddr_t)pf->page + pf->size);

		pidx = PI_IDX(index);
		if (prev_dir != NULL && PD_IDX(prev_dir->dirnum) >= pidx)
			prev_dir = NULL;	/* Will be wiped out below ! */

		for (pi = pf->pdir; pi != NULL && PD_IDX(pi->dirnum) < pidx;
		    pi = pi->next)
			;

		spi = pi;
		if (pi != NULL && PD_IDX(pi->dirnum) == pidx) {
			pd = pi->base;

			for (i = index; i <= lidx;) {
				if (pd[PI_OFF(i)] != MALLOC_NOT_MINE) {
					pd[PI_OFF(i)] = MALLOC_NOT_MINE;
#ifdef MALLOC_EXTRA_SANITY
					if (!PD_OFF(pi->dirnum)) {
						wrterror("(ES): pages directory underflow");
						errno = EFAULT;
						return;
					}
#endif /* MALLOC_EXTRA_SANITY */
					pi->dirnum--;
				}
#ifdef MALLOC_EXTRA_SANITY
				else
					wrtwarning("(ES): page already unmapped");
#endif /* MALLOC_EXTRA_SANITY */
				i++;
				if (!PI_OFF(i)) {
					/*
					 * If no page in that dir, free
					 * directory page.
					 */
					if (!PD_OFF(pi->dirnum)) {
						/* Remove from list. */
						if (spi == pi)
							spi = pi->prev;
						if (pi->prev != NULL)
							pi->prev->next = pi->next;
						if (pi->next != NULL)
							pi->next->prev = pi->prev;
						pi = pi->next;
						munmap(pd, malloc_pagesize);
					} else
						pi = pi->next;
					if (pi == NULL ||
					    PD_IDX(pi->dirnum) != PI_IDX(i))
						break;
					pd = pi->base;
				}
			}
			if (pi && !PD_OFF(pi->dirnum)) {
				/* Resulting page dir is now empty. */
				/* Remove from list. */
				if (spi == pi)	/* Update spi only if first. */
					spi = pi->prev;
				if (pi->prev != NULL)
					pi->prev->next = pi->next;
				if (pi->next != NULL)
					pi->next->prev = pi->prev;
				pi = pi->next;
				munmap(pd, malloc_pagesize);
			}
		}
		if (pi == NULL && malloc_brk == tail) {
			/* Resize down the malloc upper boundary. */
			last_index = index - 1;
			malloc_brk = index2ptr(index);
		}

		/* XXX: We could realloc/shrink the pagedir here I guess. */
		if (pf->size == 0) {	/* Remove from free-list as well. */
			if (px)
				ifree(px);
			if ((px = pf->prev) != &free_list) {
				if (pi == NULL && last_index == (index - 1)) {
					if (spi == NULL) {
						malloc_brk = NULL;
						i = 11;
					} else {
						pd = spi->base;
						if (PD_IDX(spi->dirnum) < pidx)
							index =
							    ((PD_IDX(spi->dirnum) + 1) *
							    pdi_mod) - 1;
						for (pi = spi, i = index;
						    pd[PI_OFF(i)] == MALLOC_NOT_MINE;
						    i--)
#ifdef MALLOC_EXTRA_SANITY
							if (!PI_OFF(i)) {
								pi = pi->prev;
								if (pi == NULL || i == 0)
									break;
								pd = pi->base;
								i = (PD_IDX(pi->dirnum) + 1) * pdi_mod;
							}
#else /* !MALLOC_EXTRA_SANITY */
						{
						}
#endif /* MALLOC_EXTRA_SANITY */
						malloc_brk = index2ptr(i + 1);
					}
					last_index = i;
				}
				if ((px->next = pf->next) != NULL)
					px->next->prev = px;
			} else {
				if ((free_list.next = pf->next) != NULL)
					free_list.next->prev = &free_list;
			}
			px = pf;
			last_dir = prev_dir;
			prev_dir = NULL;
		}
	}
not_return:
	if (pt != NULL)
		ifree(pt);
}

/*
 * Free a chunk, and possibly the page it's on, if the page becomes empty.
 */

/* ARGSUSED */
static __inline__ void
free_bytes(void *ptr, u_long index, struct pginfo * info)
{
	struct pginfo	**mp, **pd;
	struct pdinfo	*pi;
#ifdef	MALLOC_EXTRA_SANITY
	u_long		pidx;
#endif	/* MALLOC_EXTRA_SANITY */
	void		*vp;
	long		i;

	/* Find the chunk number on the page */
	i = ((u_long) ptr & malloc_pagemask) >> info->shift;

	if ((u_long) ptr & ((1UL << (info->shift)) - 1)) {
		wrtwarning("modified (chunk-) pointer");
		return;
	}
	if (info->bits[i / MALLOC_BITS] & (1UL << (i % MALLOC_BITS))) {
		wrtwarning("chunk is already free");
		return;
	}
	if (malloc_junk && info->size != 0)
		memset(ptr, SOME_JUNK, (size_t)info->size);

	info->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);
	info->free++;

	if (info->size != 0)
		mp = page_dir + info->shift;
	else
		mp = page_dir;

	if (info->free == 1) {
		/* Page became non-full */

		/* Insert in address order */
		while (*mp != NULL && (*mp)->next != NULL &&
		    (*mp)->next->page < info->page)
			mp = &(*mp)->next;
		info->next = *mp;
		*mp = info;
		return;
	}
	if (info->free != info->total)
		return;

	/* Find & remove this page in the queue */
	while (*mp != info) {
		mp = &((*mp)->next);
#ifdef MALLOC_EXTRA_SANITY
		if (!*mp) {
			wrterror("(ES): Not on queue");
			errno = EFAULT;
			return;
		}
#endif /* MALLOC_EXTRA_SANITY */
	}
	*mp = info->next;

	/* Free the page & the info structure if need be */
	pdir_lookup(ptr2index(info->page), &pi);
#ifdef MALLOC_EXTRA_SANITY
	pidx = PI_IDX(ptr2index(info->page));
	if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
		wrterror("(ES): mapped pages not found in directory");
		errno = EFAULT;
		return;
	}
#endif /* MALLOC_EXTRA_SANITY */
	if (pi != last_dir) {
		prev_dir = last_dir;
		last_dir = pi;
	}
	pd = pi->base;
	pd[PI_OFF(ptr2index(info->page))] = MALLOC_FIRST;

	/* If the page was mprotected, unprotect it before releasing it */
	if (info->size == 0)
		mprotect(info->page, malloc_pagesize, PROT_READ | PROT_WRITE);

	vp = info->page;	/* Order is important ! */
	if (vp != (void *) info)
		ifree(info);
	ifree(vp);
}

static void
ifree(void *ptr)
{
	struct pginfo	*info, **pd;
	u_long		index;
#ifdef	MALLOC_EXTRA_SANITY
	u_long		pidx;
#endif	/* MALLOC_EXTRA_SANITY */
	struct pdinfo	*pi;

	if (!malloc_started) {
		wrtwarning("malloc() has never been called");
		return;
	}
	/* If we're already sinking, don't make matters any worse. */
	if (suicide)
		return;

	if (malloc_ptrguard && PTR_ALIGNED(ptr))
		ptr = (char *) ptr - PTR_GAP;

	index = ptr2index(ptr);

	if (index < malloc_pageshift) {
		warnx("(%p)", ptr);
		wrtwarning("ifree: junk pointer, too low to make sense");
		return;
	}
	if (index > last_index) {
		warnx("(%p)", ptr);
		wrtwarning("ifree: junk pointer, too high to make sense");
		return;
	}
	pdir_lookup(index, &pi);
#ifdef MALLOC_EXTRA_SANITY
	pidx = PI_IDX(index);
	if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
		wrterror("(ES): mapped pages not found in directory");
		errno = EFAULT;
		return;
	}
#endif /* MALLOC_EXTRA_SANITY */
	if (pi != last_dir) {
		prev_dir = last_dir;
		last_dir = pi;
	}
	pd = pi->base;
	info = pd[PI_OFF(index)];

	if (info < MALLOC_MAGIC)
		free_pages(ptr, index, info);
	else
		free_bytes(ptr, index, info);

	/* does not matter if malloc_bytes fails */
	if (px == NULL)
		px = malloc_bytes(sizeof *px);

	return;
}

/*
 * Common function for handling recursion.  Only
 * print the error message once, to avoid making the problem
 * potentially worse.
 */
static void
malloc_recurse(void)
{
	static int	noprint;

	if (noprint == 0) {
		noprint = 1;
		wrtwarning("recursive call");
	}
	malloc_active--;
	_MALLOC_UNLOCK();
	errno = EDEADLK;
}

/*
 * These are the public exported interface routines.
 */
void *
malloc(size_t size)
{
	void		*r;

	if (!align)
	_MALLOC_LOCK();
	malloc_func = " in malloc():";
	if (malloc_active++) {
		malloc_recurse();
		return (NULL);
	}
	r = imalloc(size);
	UTRACE(0, size, r);
	malloc_active--;
	if (!align)
	_MALLOC_UNLOCK();
	if (malloc_xmalloc && r == NULL) {
		wrterror("out of memory");
		errno = ENOMEM;
	}
	return (r);
}

void
free(void *ptr)
{
	/* This is legal. XXX quick path */
	if (ptr == NULL)
		return;

	_MALLOC_LOCK();
	malloc_func = " in free():";
	if (malloc_active++) {
		malloc_recurse();
		return;
	}
	ifree(ptr);
	UTRACE(ptr, 0, 0);
	malloc_active--;
	_MALLOC_UNLOCK();
	return;
}

void *
realloc(void *ptr, size_t size)
{
	void		*r;

	_MALLOC_LOCK();
	malloc_func = " in realloc():";
	if (malloc_active++) {
		malloc_recurse();
		return (NULL);
	}

	if (ptr == NULL)
		r = imalloc(size);
	else
		r = irealloc(ptr, size);

	UTRACE(ptr, size, r);
	malloc_active--;
	_MALLOC_UNLOCK();
	if (malloc_xmalloc && r == NULL) {
		wrterror("out of memory");
		errno = ENOMEM;
	}
	return (r);
}

#ifndef SIZE_MAX
//#if defined(__i386__)||defined(__arm__)||defined(__powerpc__)
//#define SIZE_MAX 0xffffffff
//#endif
//#if defined(__x86_64__)
//#define SIZE_MAX 0xffffffffffffffff
//#endif
#define SIZE_MAX SIZE_T_MAX
#endif

void *
calloc(size_t num, size_t size)
{
	void *p;
	
	if (num && SIZE_MAX / num < size) {
		fprintf(stderr,"OOOOPS");
		errno = ENOMEM;
		return NULL;
	}
	size *= num;
	p = malloc(size);
	if (p)
		memset(p, 0, size);
	return(p);
}

static int ispowerof2 (size_t a) {
	size_t b;
	for (b = 1ULL << (sizeof(size_t)*NBBY - 1); b > 1; b >>= 1)
	  if (b == a)
		return 1;
	return 0;
}

int posix_memalign(void **memptr, size_t alignment, size_t size)
{
	void *r;
	if ((alignment < PTR_SIZE) || (alignment%PTR_SIZE != 0)) return EINVAL;
	if (!ispowerof2(alignment)) return EINVAL;
	if (alignment < malloc_minsize) alignment = malloc_minsize;
	size_t max = alignment > size ? alignment : size;
	if (alignment <= malloc_pagesize)
		r = malloc(max);
	else {
		_MALLOC_LOCK();
		align = 1;
		g_alignment = alignment;
		r = malloc(size);
		align=0;
		_MALLOC_UNLOCK();
	}
	*memptr = r;
	if (!r) return ENOMEM;
	return 0;
}

void *memalign(size_t boundary, size_t size)
{
	void *r;
	posix_memalign(&r, boundary, size);
	return r;
}

void *valloc(size_t size)
{
	void *r;
	posix_memalign(&r, malloc_pagesize, size);
	return r;
}

size_t malloc_good_size(size_t size)
{
	if (size == 0) {
		return 1;
	} else if (size <= malloc_maxsize) {
		int i, j;
		/* round up to the nearest power of 2, with same approach
		 * as malloc_bytes() uses. */
		j = 1;
		i = size - 1;
		while (i >>= 1)
			j++;
		return ((size_t)1) << j;
	} else {
		return pageround(size);
	}
}