malloc.c

linux下用PCMCIA无线网卡虚拟无线AP的程序源码

/*
  malloc - heap manager based on heavy use of virtual memory management.
  Copyright (C) 1998   Valery Shchedrin

  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Library General Public
  License as published by the Free Software Foundation; either
  version 2 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
  Library General Public License for more details.

  You should have received a copy of the GNU Library General Public
  License along with this library; if not, write to the Free
  Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  MA 02111-1307, USA
  
  Public Functions:
  
  void *malloc(size_t size);
  
    Allocates `size` bytes
    returns NULL if no free memory available
  
  void *calloc(size_t unit, size_t quantity);
  
    Allocates `quantity*unit` zeroed bytes via internal malloc call
  
  void *realloc(void *ptr, size_t size);
  
    Reallocates already allocated block `ptr`, if `ptr` is not valid block
    then it works as malloc. NULL is returned if no free memory available
  
  void *_realloc_no_move(void *ptr, size_t size);
  
    Reallocates already allocated block `ptr`, if `ptr` is not valid block
    or if reallocation can't be done with shrinking/expanding already
    allocated block NULL is returned
  
  void free(void *ptr);
  
    Frees already allocated block, if `ptr` is incorrect one nothing will
    happen.
*/

/*
 * Manuel Novoa III         Jan 2001
 *
 * Modified to decrease object sizes.
 *   Broke into independent object files.
 *   Converted INIT_BLOCK() and FREE_MEM_DEL_BLOCK() from macros to functions.
 */

#include <features.h>
#ifndef _XOPEN_SOURCE
#define _XOPEN_SOURCE
#endif
#include <sys/types.h>
#include <unistd.h>
#include <limits.h>
#include <sys/time.h>
#include <asm/page.h>
#include <unistd.h>
#include <sys/mman.h>
#include <string.h>
#include "malloc.h"
#include <stdio.h>

#define M_DOTRIMMING 1
#define M_MULTITHREADED 0

#define VALLOC_MSTART  ((void*)0x1c000000)
#define LARGE_MSTART   ((void*)0x19000000)
#define HUNK_MSTART    ((void*)0x18000000)
#define HUNK_MSIZE     M_PAGESIZE
#define HUNK_ID        0x99171713

/* alignment of allocations > HUNK_THRESHOLD */
#define MALLOC_ALIGN    4

/* allocations < HUNK_THRESHOLD will not be aligned */
#define HUNK_THRESHOLD  4

/*up to HUNK_MAXSIZE blocks will be joined together to decrease memory waste*/
#define HUNK_MAXSIZE 128

/* returns value not less than size, aligned to MALLOC_ALIGN */
#define ALIGN(size) (((size)+(MALLOC_ALIGN)-1)&(~((MALLOC_ALIGN)-1)))

/* aligns s or p to page boundaries */
#define PAGE_ALIGN(s) (((s)+M_PAGESIZE-1)&(~(M_PAGESIZE-1)))
#define PAGE_ALIGNP(p) ((char*)PAGE_ALIGN((unsigned)(p)))
#define PAGE_DOWNALIGNP(p) ((char*)(((unsigned)(p))&(~(M_PAGESIZE-1))))

/* returns v * 2 for your machine (speed-up) */
#define MUL2(v)  ((v)*2)

/* does v *= 8 for your machine (speed-up) */
#define EMUL8(v) v*=8

/* does v/8 for your machind (speed-up) */
#define DIV8(v)  ((v)/8)

#if M_MULTITHREADED
#error This version does not support threads
#else
typedef int mutex_t;

#define mutex_lock(x)
#define mutex_unlock(x)
#define mutex_init(x)
#define MUTEX_INITIALIZER 0
//static mutex_t malloc_lock = MUTEX_INITIALIZER;
#endif

extern int __malloc_initialized;

#ifdef L__malloc_init
int __malloc_initialized = -1;

 /* -1 == uninitialized, 0 == initializing, 1 == initialized */
#endif

#ifndef MAP_FAILED
#define MAP_FAILED ((void*)-1)
#endif

#if defined(MAP_ANONYMOUS) && !defined(MAP_ANON)
#define MAP_ANON MAP_ANONYMOUS
#endif

#ifndef NULL
#define NULL ((void*)0)
#endif

/* guess pagesize */
#define M_PAGESIZE getpagesize()

/* HUNK MANAGER */

typedef struct Hunk_s Hunk_t;

struct Hunk_s {					/* Hunked block - 8 byte overhead */
	int id;						/* unique id */
	unsigned int total:12, used:12, size:8;
	Hunk_t *next;				/* next free in __free_h */
};

#define usagemap(h) (((unsigned char *)(h))+sizeof(Hunk_t))
#define hunk_ptr(h) (((char*)(h))+sizeof(Hunk_t)+ALIGN(DIV8(h->total+7)))
#define hunk(h)  ((Hunk_t*)(h))

extern Hunk_t *__free_h[HUNK_MAXSIZE + 1];
extern int __total_h[HUNK_MAXSIZE + 1];

#ifdef L__malloc_init
Hunk_t *__free_h[HUNK_MAXSIZE + 1];	/* free hash */
int __total_h[HUNK_MAXSIZE + 1];	/* Hunk_t's `total` member */
#endif

extern void *__hunk_alloc(int size);

#ifdef L_malloc
/* __hunk_alloc allocates <= HUNK_MAXSIZE blocks */
void *__hunk_alloc(int size)
{
	Hunk_t *p;
	unsigned long *cpl;
	int i, c;

	//	if (size >= HUNK_THRESHOLD)
	size = ALIGN(size);

	/* Look for already allocated hunkblocks */
	if ((p = __free_h[size]) == NULL) {
		if (
			(p =
			 (Hunk_t *) mmap(HUNK_MSTART, HUNK_MSIZE,
							 PROT_READ | PROT_WRITE,
#ifdef __UCLIBC_HAS_MMU__
							 MAP_PRIVATE | MAP_ANONYMOUS
#else
							 MAP_SHARED | MAP_ANONYMOUS
#endif
							 , 0, 0)) == (Hunk_t *) MAP_FAILED)
		  // {
		  //  printf("hunk_alloc failed: %d, %d\n", size, errno);
			return NULL;
		  // }
		memset(p, 0, HUNK_MSIZE);
		p->id = HUNK_ID;
		p->total = __total_h[size];
		/* p->used = 0; */
		p->size = size;
		/* p->next = (Hunk_t*)NULL; */
		/* memset(usagemap(p), 0, bound); */
		__free_h[size] = p;
	}

	/* Locate free point in usagemap */
	
	/* First find a word where not all the bits are set */
	for (cpl = (unsigned long *) usagemap(p); *cpl == 0xFFFFFFFF; cpl++);

	/* Remember the byte position of that word */
	i = ((unsigned char *) cpl) - usagemap(p);

	/* Now find find a free bit in the word using binary search */
	if (*(unsigned short *) cpl != 0xFFFF) {

		if (*(unsigned char *) cpl == 0xFF) {
			c = *(((unsigned char *) cpl) + 1);
			i++;
		}
		else
		  {
		    c = *(unsigned char *) cpl;
		  }
	} else {
		i += 2;
		c = *(((unsigned char *) cpl) + 2);
		if (c == 0xFF) {
			c = *(((unsigned char *) cpl) + 3);
			i++;
		}
	}
	
	/*
	 * Multiply i by 8 for the bit position
	 * Further down, we divide by 8 again to find the byte position
	 */
	EMUL8(i);
	
	/* If bottom nibble is set, shift down the top nibble */
	if ((c & 0xF) == 0xF) {
		c >>= 4;
		i += 4;
	}
	
	/* If bottom 2 bits are set, shift down the top two */
	if ((c & 0x3) == 0x3) {
		c >>= 2;
		i += 2;
	}
	
	/* Check which one of the two bits is set */
	if (c & 1)
		i++;

	usagemap(p)[DIV8(i)] |= (1 << (i & 7));	/* set bit */

	/* Increment counter and update hashes */
	if (++p->used == p->total) {
		__free_h[p->size] = p->next;
		p->next = NULL;
	}
	
	// fprintf(stderr, "hunk_alloc: i=%d, p->size=%d, p=%p\n", i, p->size, p);
	return hunk_ptr(p) + i * p->size;
}
#endif							/* L_malloc */

extern void __hunk_free(char *ptr);

#ifdef L__free_support
/* __hunk_free frees blocks allocated by __hunk_alloc */
void __hunk_free(char *ptr)
{
	unsigned char *up;
	int i, v;
	Hunk_t *h;

	if (!ptr)
		return;

	h = (Hunk_t *) PAGE_DOWNALIGNP(ptr);

	/* Validate `ptr` */
	if (h->id != HUNK_ID)
		return;
	v = ptr - hunk_ptr(h);
	i = v / h->size;
	if (v % h->size != 0 || i < 0 || i >= h->total)
		return;

	/* Update `usagemap` */
	up = &(usagemap(h)[DIV8(i)]);
	i = 1 << (i & 7);
	if (!(*up & i))
		return;
	*up ^= i;

	/* Update hunk counters */
	if (h->used == h->total) {
		if (--h->used) {		/* insert into __free_h */
			h->next = __free_h[h->size];
			__free_h[h->size] = h;
		}						/* else - it will be unmapped */
	} else {
		if (!--h->used) {		/* delete from __free_h - will be __bl_freed */
			Hunk_t *p, *pp;

			for (p = __free_h[h->size], pp = NULL; p != h;
				 pp = p, p = p->next);
			if (!pp)
				__free_h[h->size] = p->next;
			else
				pp->next = p->next;
		}
	}

	/* Unmap empty Hunk_t */
	if (!h->used)
		munmap((void *) h, HUNK_MSIZE);
}
#endif							/* L__free_support */

/* BLOCK MANAGER */

typedef struct Block_s Block_t;

struct Block_s {				/* 32-bytes long control structure (if 4-byte aligned) */
	char *ptr;					/* pointer to related data */
	Block_t *next;				/* next in free_mem list */
	Block_t *l_free_mem, *r_free_mem;	/* left & right subtrees of <free_mem> */
	Block_t *l_ptrs, *r_ptrs;	/* left & right subtrees of <ptrs> */
	size_t size;				/* size - divided by align */

	/* packed 4-byte attributes */
/* { */
	signed char bal_free_mem:8;	/* balance of <free_mem> subtree */
	signed char bal_ptrs:8;		/* balance of <ptrs> subtree */
	unsigned int used:1;		/* used/free state of the block */
	unsigned int broken:1;		/* 1 if previous block can't be merged with it */
/* } */
};

extern Block_t *__bl_last;		/* last mmapped block */

#ifdef L__malloc_init
Block_t *__bl_last;				/* last mmapped block */
#endif

#define bl_get() __hunk_alloc(sizeof(Block_t))
#define bl_rel(p) __hunk_free((char*)p)

extern Block_t *__Avl_Block_tfree_mem_tree;
extern Block_t *__free_mem_ins(Block_t * data);
extern void __free_mem_del(Block_t * data);
extern void __free_mem_replace(Block_t * data);
extern Block_t *__Avl_Block_tptrs_tree;
extern Block_t *__ptrs_ins(Block_t * data);
extern void __ptrs_del(Block_t * data);

extern void __bl_uncommit(Block_t * b);
extern void __bl_free(Block_t * b);

/* like C++ templates ;-) */
#include "avlmacro.h"

#define FREE_MEM_COMPARE(i,a,b) \
{ \
  if ( (a)->size < (b)->size ) { \
     i = -1; \
  } else if ( (a)->size > (b)->size ) { \
     i = 1; \
  } else { \
     i = 0; \
  } \
}

#define PTRS_COMPARE(i,a,b) \
{ \
  if ( (a)->ptr < (b)->ptr ) { \
     i = -1; \
  } else if ( (a)->ptr > (b)->ptr ) { \
     i = 1; \
  } else { \
     i = 0; \
  } \
}

#ifdef L__avl_support
Avl_Tree(free_mem, Block_t, free_mem, FREE_MEM_COMPARE)
	Avl_Tree_no_replace(ptrs, Block_t, ptrs, PTRS_COMPARE)
#endif
#define free_mem_root Avl_Root(Block_t, free_mem)
#define ptrs_root Avl_Root(Block_t, ptrs)
/* pp is freed block */
#define FREE_MEM_DEL_BLOCK(pp,p) {p = __free_mem_del_block(pp,p);}
extern Block_t *__free_mem_del_block(Block_t * pp, Block_t * p);

#ifdef L_malloc
Block_t *__free_mem_del_block(Block_t * pp, Block_t * p)
{
	for (p = free_mem_root;;)
		if (p->size > pp->size)
			p = p->l_free_mem;
		else if (p->size < pp->size)
			p = p->r_free_mem;
		else
			break;
	if (p == pp) {
		if (pp->next)
			__free_mem_replace(pp->next);
		else
			__free_mem_del(pp);
	} else {
		for (; p->next != pp; p = p->next);
		p->next = pp->next;
	}
	return p;
}
#endif							/* L_malloc */

#define FREE_MEM_INS_BLOCK(pp) \
{ \
  if ((p = __free_mem_ins(pp)) != NULL)\
  {\
    pp->next = p->next;\
    p->next = pp;\
  }\
  else pp->next = NULL; \
}

/* `b` is current block, `pp` is next block */
#define COMBINE_BLOCKS(b,pp) \
{\
  __ptrs_del(pp); \
  b->size += pp->size; \
  if (pp == __bl_last) __bl_last = b; \
  bl_rel(pp); \
}

/* initializes new block b */
#define INIT_BLOCK(b, pppp, sz) { p = __init_block(b, pppp, sz); }

extern Block_t *__init_block(Block_t * b, char *pppp, size_t sz);