openbsd_malloc_linux.c

关于tor匿名通信的源代码

	struct pginfo	*bp, **pd;
	struct pdinfo	*pi;
#ifdef	MALLOC_EXTRA_SANITY
	u_long		pidx;
#endif	/* MALLOC_EXTRA_SANITY */
	void		*pp;
	long		i, k;
	size_t		l;

	/* Allocate a new bucket */
	pp = malloc_pages((size_t) malloc_pagesize);
	if (pp == NULL)
		return (0);

	/* Find length of admin structure */
	l = sizeof *bp - sizeof(u_long);
	l += sizeof(u_long) *
	    (((malloc_pagesize >> bits) + MALLOC_BITS - 1) / MALLOC_BITS);

	/* Don't waste more than two chunks on this */

	/*
	 * If we are to allocate a memory protected page for the malloc(0)
	 * case (when bits=0), it must be from a different page than the
	 * pginfo page.
	 * --> Treat it like the big chunk alloc, get a second data page.
	 */
	if (bits != 0 && (1UL << (bits)) <= l + l) {
		bp = (struct pginfo *) pp;
	} else {
		bp = (struct pginfo *) imalloc(l);
		if (bp == NULL) {
			ifree(pp);
			return (0);
		}
	}

	/* memory protect the page allocated in the malloc(0) case */
	if (bits == 0) {
		bp->size = 0;
		bp->shift = 1;
		i = malloc_minsize - 1;
		while (i >>= 1)
			bp->shift++;
		bp->total = bp->free = malloc_pagesize >> bp->shift;
		bp->page = pp;

		k = mprotect(pp, malloc_pagesize, PROT_NONE);
		if (k < 0) {
			ifree(pp);
			ifree(bp);
			return (0);
		}
	} else {
		bp->size = (1UL << bits);
		bp->shift = bits;
		bp->total = bp->free = malloc_pagesize >> bits;
		bp->page = pp;
	}

	/* set all valid bits in the bitmap */
	k = bp->total;
	i = 0;

	/* Do a bunch at a time */
	for (; (k - i) >= MALLOC_BITS; i += MALLOC_BITS)
		bp->bits[i / MALLOC_BITS] = ~0UL;

	for (; i < k; i++)
		bp->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);

	k = (long)l;
	if (bp == bp->page) {
		/* Mark the ones we stole for ourselves */
		for (i = 0; k > 0; i++) {
			bp->bits[i / MALLOC_BITS] &= ~(1UL << (i % MALLOC_BITS));
			bp->free--;
			bp->total--;
			k -= (1 << bits);
		}
	}
	/* MALLOC_LOCK */

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

	bp->next = page_dir[bits];
	page_dir[bits] = bp;

	/* MALLOC_UNLOCK */
	return (1);
}

/*
 * Allocate a fragment
 */
static void *
malloc_bytes(size_t size)
{
	int		i, j;
	size_t		k;
	u_long		u, *lp;
	struct pginfo	*bp;

	/* Don't bother with anything less than this */
	/* unless we have a malloc(0) requests */
	if (size != 0 && size < malloc_minsize)
		size = malloc_minsize;

	/* Find the right bucket */
	if (size == 0)
		j = 0;
	else {
		j = 1;
		i = size - 1;
		while (i >>= 1)
			j++;
	}

	/* If it's empty, make a page more of that size chunks */
	if (page_dir[j] == NULL && !malloc_make_chunks(j))
		return (NULL);

	bp = page_dir[j];

	/* Find first word of bitmap which isn't empty */
	for (lp = bp->bits; !*lp; lp++);

	/* Find that bit, and tweak it */
	u = 1;
	k = 0;
	while (!(*lp & u)) {
		u += u;
		k++;
	}

	if (malloc_guard) {
		/* Walk to a random position. */
//		i = arc4random() % bp->free;
		i = rand() % bp->free;
		while (i > 0) {
			u += u;
			k++;
			if (k >= MALLOC_BITS) {
				lp++;
				u = 1;
				k = 0;
			}
#ifdef MALLOC_EXTRA_SANITY
			if (lp - bp->bits > (bp->total - 1) / MALLOC_BITS) {
				wrterror("chunk overflow");
				errno = EFAULT;
				return (NULL);
			}
#endif /* MALLOC_EXTRA_SANITY */
			if (*lp & u)
				i--;
		}
	}
	*lp ^= u;

	/* If there are no more free, remove from free-list */
	if (!--bp->free) {
		page_dir[j] = bp->next;
		bp->next = NULL;
	}
	/* Adjust to the real offset of that chunk */
	k += (lp - bp->bits) * MALLOC_BITS;
	k <<= bp->shift;

	if (malloc_junk && bp->size != 0)
		memset((char *)bp->page + k, SOME_JUNK, (size_t)bp->size);

	return ((u_char *) bp->page + k);
}

/*
 * Magic so that malloc(sizeof(ptr)) is near the end of the page.
 */
#define	PTR_GAP		(malloc_pagesize - sizeof(void *))
#define	PTR_SIZE	(sizeof(void *))
#define	PTR_ALIGNED(p)	(((unsigned long)p & malloc_pagemask) == PTR_GAP)

/*
 * Allocate a piece of memory
 */
static void *
imalloc(size_t size)
{
	void		*result;
	int		ptralloc = 0;

	if (!malloc_started)
		malloc_init();

	if (suicide)
		abort();

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

	if (malloc_ptrguard && size == PTR_SIZE) {
		ptralloc = 1;
		size = malloc_pagesize;
	}
	if ((size + malloc_pagesize) < size) {	/* Check for overflow */
		result = NULL;
		errno = ENOMEM;
	} else if (size <= malloc_maxsize)
		result = malloc_bytes(size);
	else
		result = malloc_pages(size);

	if (malloc_abort == 1 && result == NULL)
		wrterror("allocation failed");

	if (malloc_zero && result != NULL)
		memset(result, 0, size);

	if (result && ptralloc)
		return ((char *) result + PTR_GAP);
	return (result);
}

/*
 * Change the size of an allocation.
 */
static void *
irealloc(void *ptr, size_t size)
{
	void		*p;
	size_t		osize;
	u_long		index, i;
	struct pginfo	**mp;
	struct pginfo	**pd;
	struct pdinfo	*pi;
#ifdef	MALLOC_EXTRA_SANITY
	u_long		pidx;
#endif	/* MALLOC_EXTRA_SANITY */

	if (suicide)
		abort();

	if (!malloc_started) {
		wrtwarning("malloc() has never been called");
		return (NULL);
	}
	if (malloc_ptrguard && PTR_ALIGNED(ptr)) {
		if (size <= PTR_SIZE)
			return (ptr);

		p = imalloc(size);
		if (p)
			memcpy(p, ptr, PTR_SIZE);
		ifree(ptr);
		return (p);
	}
	index = ptr2index(ptr);

	if (index < malloc_pageshift) {
		wrtwarning("junk pointer, too low to make sense");
		return (NULL);
	}
	if (index > last_index) {
		wrtwarning("junk pointer, too high to make sense");
		return (NULL);
	}
	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 (NULL);
	}
#endif /* MALLOC_EXTRA_SANITY */
	if (pi != last_dir) {
		prev_dir = last_dir;
		last_dir = pi;
	}
	pd = pi->base;
	mp = &pd[PI_OFF(index)];

	if (*mp == MALLOC_FIRST) {	/* Page allocation */

		/* Check the pointer */
		if ((u_long) ptr & malloc_pagemask) {
			wrtwarning("modified (page-) pointer");
			return (NULL);
		}
		/* Find the size in bytes */
		i = index;
		if (!PI_OFF(++i)) {
			pi = pi->next;
			if (pi != NULL && PD_IDX(pi->dirnum) != PI_IDX(i))
				pi = NULL;
			if (pi != NULL)
				pd = pi->base;
		}
		for (osize = malloc_pagesize;
		    pi != NULL && pd[PI_OFF(i)] == MALLOC_FOLLOW;) {
			osize += malloc_pagesize;
			if (!PI_OFF(++i)) {
				pi = pi->next;
				if (pi != NULL && PD_IDX(pi->dirnum) != PI_IDX(i))
					pi = NULL;
				if (pi != NULL)
					pd = pi->base;
			}
		}

		if (!malloc_realloc && size <= osize &&
		    size > osize - malloc_pagesize) {
			if (malloc_junk)
				memset((char *)ptr + size, SOME_JUNK, osize - size);
			return (ptr);	/* ..don't do anything else. */
		}
	} else if (*mp >= MALLOC_MAGIC) {	/* Chunk allocation */

		/* Check the pointer for sane values */
		if ((u_long) ptr & ((1UL << ((*mp)->shift)) - 1)) {
			wrtwarning("modified (chunk-) pointer");
			return (NULL);
		}
		/* Find the chunk index in the page */
		i = ((u_long) ptr & malloc_pagemask) >> (*mp)->shift;

		/* Verify that it isn't a free chunk already */
		if ((*mp)->bits[i / MALLOC_BITS] & (1UL << (i % MALLOC_BITS))) {
			wrtwarning("chunk is already free");
			return (NULL);
		}
		osize = (*mp)->size;

		if (!malloc_realloc && size <= osize &&
		    (size > osize / 2 || osize == malloc_minsize)) {
			if (malloc_junk)
				memset((char *) ptr + size, SOME_JUNK, osize - size);
			return (ptr);	/* ..don't do anything else. */
		}
	} else {
		wrtwarning("irealloc: pointer to wrong page");
		return (NULL);
	}

	p = imalloc(size);

	if (p != NULL) {
		/* copy the lesser of the two sizes, and free the old one */
		/* Don't move from/to 0 sized region !!! */
		if (osize != 0 && size != 0) {
			if (osize < size)
				memcpy(p, ptr, osize);
			else
				memcpy(p, ptr, size);
		}
		ifree(ptr);
	}
	return (p);
}

/*
 * Free a sequence of pages
 */
static __inline__ void
free_pages(void *ptr, u_long index, struct pginfo * info)
{
	u_long		i, pidx, lidx;
	size_t		l, cachesize = 0;
	struct pginfo	**pd;
	struct pdinfo	*pi, *spi;
	struct pgfree	*pf, *pt = NULL;
	caddr_t		tail;

	if (info == MALLOC_FREE) {
		wrtwarning("page is already free");
		return;
	}
	if (info != MALLOC_FIRST) {
		wrtwarning("free_pages: pointer to wrong page");
		return;
	}
	if ((u_long) ptr & malloc_pagemask) {
		wrtwarning("modified (page-) pointer");
		return;
	}
	/* Count how many pages and mark them free at the same time */
	pidx = PI_IDX(index);
	pdir_lookup(index, &pi);
#ifdef MALLOC_EXTRA_SANITY
	if (pi == NULL || PD_IDX(pi->dirnum) != pidx) {
		wrterror("(ES): mapped pages not found in directory");
		errno = EFAULT;
		return;
	}
#endif /* MALLOC_EXTRA_SANITY */

	spi = pi;		/* Save page index for start of region. */

	pd = pi->base;
	pd[PI_OFF(index)] = MALLOC_FREE;
	i = 1;
	if (!PI_OFF(index + i)) {
		pi = pi->next;
		if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(index + i))
			pi = NULL;
		else
			pd = pi->base;
	}
	while (pi != NULL && pd[PI_OFF(index + i)] == MALLOC_FOLLOW) {
		pd[PI_OFF(index + i)] = MALLOC_FREE;
		i++;
		if (!PI_OFF(index + i)) {
			if ((pi = pi->next) == NULL ||
			    PD_IDX(pi->dirnum) != PI_IDX(index + i))
				pi = NULL;
			else
				pd = pi->base;
		}
	}

	l = i << malloc_pageshift;

	if (malloc_junk)
		memset(ptr, SOME_JUNK, l);

	malloc_used -= l;
	malloc_guarded -= malloc_guard;
	if (malloc_guard) {
#ifdef MALLOC_EXTRA_SANITY
		if (pi == NULL || PD_IDX(pi->dirnum) != PI_IDX(index + i)) {
			wrterror("(ES): hole in mapped pages directory");
			errno = EFAULT;
			return;
		}
#endif /* MALLOC_EXTRA_SANITY */
		pd[PI_OFF(index + i)] = MALLOC_FREE;
		l += malloc_guard;
	}
	tail = (caddr_t)ptr + l;

	if (malloc_hint)
		madvise(ptr, l, MADV_FREE);

	if (malloc_freeprot)
		mprotect(ptr, l, PROT_NONE);

	/* Add to free-list. */
	if (px == NULL && (px = malloc_bytes(sizeof *px)) == NULL)
			goto not_return;
	px->page = ptr;
	px->pdir = spi;
	px->size = l;

	if (free_list.next == NULL) {
		/* Nothing on free list, put this at head. */
		px->next = NULL;
		px->prev = &free_list;
		free_list.next = px;
		pf = px;
		px = NULL;
	} else {
		/*
		 * Find the right spot, leave pf pointing to the modified
		 * entry.
		 */

		/* Race ahead here, while calculating cache size. */
		for (pf = free_list.next;
		    (caddr_t)ptr > ((caddr_t)pf->page + pf->size)
		    && pf->next != NULL;
		    pf = pf->next)
			cachesize += pf->size;

		/* Finish cache size calculation. */
		pt = pf;
		while (pt) {
			cachesize += pt->size;
			pt = pt->next;
		}

		if ((caddr_t)pf->page > tail) {
			/* Insert before entry */
			px->next = pf;
			px->prev = pf->prev;
			pf->prev = px;
			px->prev->next = px;
			pf = px;
			px = NULL;
		} else if (((caddr_t)pf->page + pf->size) == ptr) {
			/* Append to the previous entry. */
			cachesize -= pf->size;
			pf->size += l;
			if (pf->next != NULL &&